记录编号	234977	评测结果	AAAAAATTTT
题目名称	[HNOI 2015]开店	最终得分	60
用户昵称	stdafx.h	是否通过	未通过
代码语言	C++	运行时间	98.955 s
提交时间	2016-03-10 07:23:09	内存使用	11.89 MiB

#define maxn 150010ul

#define ll long long

#include <map>
#include <stdio.h>
#include <stdlib.h>

struct pii{ll first;int second;};
struct Edge{int v,w,nx;};
struct Edge_none_w{int v,nx;};

struct treap{
	#define null NULL
	struct node{
		node *left,*right;
		int key,fix,size_,w;ll sum,val;
		node(int _key,int _val){
			left=right=null;
			fix=rand(),val=sum=_val,key=_key,size_=w=1;
			return;
		}
		ll lsum(){return val+(left!=null?left->sum:0);}
		ll rsum(){return val+(right!=null?right->sum:0);}
		int lsize(){return w+(left!=null?left->size_:0);}
		int rsize(){return w+(right!=null?right->size_:0);}
		void update(){
			sum=val,size_=w;
			if(left!=null) sum+=left->sum,size_+=left->size_;
			if(right!=null) sum+=right->sum,size_+=right->size_;
			return;
		}
	}*root;
	treap(){root=null;return;}
	void rturn(node *&a){
		node *b=a->left;
		a->left=b->right;
		b->right=a,a=b;
		b->right->update();
		return;
	}
	void lturn(node *&a){
		node *b=a->right;
		a->right=b->left;
		b->left=a,a=b;
		b->left->update();
		return;
	}
	void insert(node *&rt,int key,int val){
		if(rt==null){rt=new node(key,val);return;}
		if(key==rt->key){rt->val+=val,rt->sum+=val,rt->w++,rt->size_++;return;}
		if(key<rt->key){
			insert(rt->left,key,val);
			if(rt->left->fix<rt->fix) rturn(rt);
		}
		else{
			insert(rt->right,key,val);
			if(rt->right->fix<rt->fix) lturn(rt);
		}
		rt->update();
		return;
	}
	void ins(int key,int val){
		insert(root,key,val);
		return;
	}
	ll ask_smaller_sum(node *rt,int p){
		if(rt==null) return 0;
		if(rt->key<p) return rt->lsum()+ask_smaller_sum(rt->right,p);
		return ask_smaller_sum(rt->left,p);
	}
	ll ask_bigger_sum(node *rt,int p){
		if(rt==null) return 0;
		if(rt->key>p) return rt->rsum()+ask_bigger_sum(rt->left,p);
		return ask_bigger_sum(rt->right,p);
	}
	int ask_smaller_size(node *rt,int p){
		if(rt==null) return 0;
		if(rt->key<p) return rt->lsize()+ask_smaller_size(rt->right,p);
		return ask_smaller_size(rt->left,p);
	}
	int ask_bigger_size(node *rt,int p){
		if(rt==null) return 0;
		if(rt->key>p) return rt->rsize()+ask_bigger_size(rt->left,p);
		return ask_bigger_size(rt->right,p);
	}
	pii query(int l,int r){
		if(root==null) return (pii){0,0};
		return (pii){
			root->sum-ask_smaller_sum(root,l)-ask_bigger_sum(root,r),
			root->size_-ask_smaller_size(root,l)-ask_bigger_size(root,r)
		};
	}
}bst[maxn];

typedef std::map<int,int> mpd;
mpd M[maxn];
Edge edge[maxn<<1],e2[maxn];
int n,q,ec,ec2,limit_age,age[maxn],dfa[maxn],headlist[maxn],h2[maxn];ll last_ans;
bool ex[maxn];

int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}

void Add_Edge(int u,int v,int w){
	edge[++ec].v=v;
	edge[ec].w=w;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

void Add_Edge2(int u,int v){
	e2[++ec2].v=v;
	e2[ec2].nx=h2[u];
	h2[u]=ec2;
	return;
}

int tree_size(int p,int fa){
	int size_=1;
	for(int i=headlist[p];i;i=edge[i].nx) if(!ex[edge[i].v]&&edge[i].v!=fa)
        size_+=tree_size(edge[i].v,p);
	return size_;
}

int gravity(int p,int fa,int tot,int &center){
	int size_=1,k;bool flag=true;
	for(int i=headlist[p];i;i=edge[i].nx) if(!ex[edge[i].v]&&edge[i].v!=fa){
		k=gravity(edge[i].v,p,tot,center);
		if((k<<1)>tot) flag=false;
		size_+=k;
	}
	if(((tot-size_)<<1)>tot) flag=false;
	if(flag) center=p;
	return size_;
}

void dfs(int p,int fa,int dis,treap &s,mpd &rt){
	s.ins(age[p],dis),rt[p]=dis;
	for(int i=headlist[p];i;i=edge[i].nx) if(!ex[edge[i].v]&&edge[i].v!=fa)
	    dfs(edge[i].v,p,dis+edge[i].w,s,rt);
	return;
}

int tree_divide(int p){
	int center,k,center_of_son;
	gravity(p,0,tree_size(p,0),center);
	ex[center]=true,M[center][center]=0;//bst saving the dist to dfa of the whole tree
	for(int i=headlist[center];i;i=edge[i].nx) if(!ex[edge[i].v]){
		treap rt;dfs(edge[i].v,0,edge[i].w,rt,M[center]);
		center_of_son=tree_divide(edge[i].v);
        bst[center_of_son]=rt;
		dfa[center_of_son]=center;
	}
	return center;
}

ll work(int x,int L,int R){
	int can_not_choose=0;pii tmp;ll cur_dis,ans=0;
	for(int i=x;i;can_not_choose=i,i=dfa[i]){
		cur_dis=M[i][x];
		if(age[i]>=L&&age[i]<=R) ans+=cur_dis;
		for(int k=h2[i];k;k=e2[k].nx){
			if(e2[k].v==can_not_choose) continue;
			tmp=bst[e2[k].v].query(L,R);
			ans+=tmp.first+tmp.second*cur_dis;
		}
	}
	return ans;
}

int main(){
	freopen("shop_hnoi2015.in","r",stdin);
	freopen("shop_hnoi2015.out","w",stdout);
    srand(19981011);/*good luck*/
	n=in(),q=in(),limit_age=in();
	for(int i=1;i<=n;i++) age[i]=in();
	for(int i=1,a,b,t;i<n;i++){
		a=in(),b=in(),t=in();
		Add_Edge(a,b,t),Add_Edge(b,a,t);
	}
	tree_divide(1);
	for(int i=1;i<=n;i++) if(dfa[i])
		Add_Edge2(dfa[i],i);
	for(int i=0,x,a,b;i<q;i++){
		x=in(),a=in(),b=in();
		a=(a+last_ans)%limit_age,b=(b+last_ans)%limit_age;
		if(a>b) a^=b,b^=a,a^=b;
		printf("%lld\n",last_ans=work(x,a,b));
	}
	return 0;
}