记录编号	393010	评测结果	AAAAAAAAAA
题目名称	[HNOI 2015]开店	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	8.090 s
提交时间	2017-04-09 18:53:47	内存使用	421.84 MiB

//BZOJ 4012
//by Cydiater
//2017.4.8
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <bitset>
#include <complex>

using namespace std;

#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;++i)
#define down(i,j,n)	for(int i=j;i>=n;--i)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"shop_hnoi2015"

const int MAXN=5e5+5;
const int oo=0x3f3f3f3f;

int N,M,val[MAXN],num[MAXN],top=0,fe[MAXN],mod;
ll sum[MAXN],pre[MAXN],dis[MAXN],tol[MAXN],ans=0;
vector<int>S[MAXN];

namespace CMT{
	int root[MAXN],cnt;
	struct tree{
		int son[2];
		ll res,tol;
		tree(){son[0]=son[1]=res=tol=0;}
	}t[MAXN<<5];
	int NewNode(int s0,int s1,ll res,ll tol){
		cnt++;
		t[cnt].son[0]=s0;t[cnt].son[1]=s1;
		t[cnt].res=res;t[cnt].tol=tol;
		return cnt;
	}
	void Build(int leftt,int rightt,int &k,int L,int R){
		k=NewNode(t[k].son[0],t[k].son[1],t[k].res,t[k].tol);
		t[k].res+=sum[min(rightt,R)]-sum[max(leftt,L)-1];
		if(leftt>=L&&rightt<=R){
			t[k].tol++;
			return;
		}
		int mid=(leftt+rightt)>>1;
		if(L<=mid)	Build(leftt,mid,t[k].son[0],L,R);
		if(R>=mid+1)	Build(mid+1,rightt,t[k].son[1],L,R);
	}
	ll Query(int leftt,int rightt,int k,int L,int R){
		if(!k)return 0;
		ll res=0;
		if(leftt>=L&&rightt<=R)	return res+t[k].res;
		res+=(sum[min(rightt,R)]-sum[max(leftt,L)-1])*t[k].tol;
		int mid=(leftt+rightt)>>1;
		if(L<=mid)	res+=Query(leftt,mid,t[k].son[0],L,R);
		if(mid+1<=R)	res+=Query(mid+1,rightt,t[k].son[1],L,R);
		return res;
	}
}using namespace CMT;

namespace Graph{
	struct edge{
		int y,next,v;
	}e[MAXN<<1];
	int LINK[MAXN],len=0,dep[MAXN],dfn[MAXN],Pos[MAXN],dfsclock=0;
	int son[MAXN],siz[MAXN],tp[MAXN],fa[MAXN];
	inline void insert(int x,int y,int v){
		e[++len].next=LINK[x];LINK[x]=len;
		e[len].y=y;e[len].v=v;
	}
	inline void Insert(int x,int y,int v){
		insert(x,y,v);
		insert(y,x,v);
	}
	void DFS1(int node,int father,int deep){
		fa[node]=father;dep[node]=deep;
		siz[node]=1;son[node]=0;fa[node]=father;
		Auto(i,node)if(e[i].y!=father){
			dis[e[i].y]=dis[node]+e[i].v;
			DFS1(e[i].y,node,deep+1);
			siz[node]+=siz[e[i].y];
			fe[e[i].y]=e[i].v;
			if(siz[e[i].y]>siz[son[node]])
				son[node]=e[i].y;
		}
	}
	void DFS2(int node,int Top){
		tp[node]=Top;Pos[node]=++dfsclock;
		dfn[dfsclock]=node;
		if(son[node])DFS2(son[node],Top);
		Auto(i,node)if(e[i].y!=son[node]&&e[i].y!=fa[node])
			DFS2(e[i].y,e[i].y);
	}
	void Go(int p,int node){
		do{
			int L=Pos[tp[node]],R=Pos[node];
			Build(1,N,root[p],L,R);
			node=fa[tp[node]];
		}while(node);
	}
}using namespace Graph;

namespace solution{
	void Prepare(){
		scanf("%d%d%d",&N,&M,&mod);
		up(i,1,N){
			scanf("%d",&val[i]);
			num[++top]=val[i];
		}
		sort(num+1,num+top+1);
		top=unique(num+1,num+top+1)-(num+1);
		up(i,1,N){
			val[i]=lower_bound(num+1,num+top+1,val[i])-num;
			S[val[i]].push_back(i);
		}
		up(i,2,N){
			int x,y,v;
			scanf("%d%d%d",&x,&y,&v);
			Insert(x,y,v);
		}
		dis[1]=0;
		DFS1(1,0,0);
		DFS2(1,1);
		sum[0]=pre[0]=tol[0]=0;
		up(i,1,N)sum[i]=sum[i-1]+fe[dfn[i]];
		up(i,1,top){
			int size=S[i].size();
			root[i]=root[i-1];
			pre[i]=pre[i-1];
			tol[i]=tol[i-1]+size;
			up(j,0,size-1){
				int node=S[i][j];
				Go(i,node);
				pre[i]+=dis[node];
			}
		}
	}
	ll Col(ll LIM,int p){
		if(LIM<=0)return 0;
		ll res=pre[LIM]+tol[LIM]*dis[p],L,R;
		do{
			L=Pos[tp[p]];
			R=Pos[p];
			res-=Query(1,N,root[LIM],L,R)*2;
			p=fa[tp[p]];
			if(p==1)break;
		}while(p);
		return res;
	}
	void Solve(){
		int L,R;
		while(M--){
			ll p,a,b;
			scanf("%lld%lld%lld",&p,&a,&b);
			L=min((a+ans)%mod,(b+ans)%mod);
			R=max((a+ans)%mod,(b+ans)%mod);
			if(R<num[1]||L>num[top]){
				ans=0;
				puts("0");
				continue;
			}
			cmin(R,num[top]);
			cmax(L,num[1]);
			ll tL=lower_bound(num+1,num+top+1,L)-num;
			ll tR=lower_bound(num+1,num+top+1,R)-num;
			if(R!=num[tR]||tR==top+1)tR--;
			L=tL;R=tR;
			ans=Col(R,p);
			ans-=Col(L-1,p);
			printf("%lld\n",ans);
		}
	}
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}