记录编号	383644	评测结果	AAAAAAAAAA
题目名称	[HNOI 2015]开店	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	20.334 s
提交时间	2017-03-16 09:14:21	内存使用	65.68 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=150010;
struct A{
	int d;
	long long w;
	A(int d,long long w):d(d),w(w){}
	bool operator<(const A &a)const{return d<a.d;}
};
void build(int,int,int,int);
int getcenter(int,int);
void getdis(int,int);
long long query(int,int,int);
vector<int>G[maxn],W[maxn];
int p[maxn],depth[maxn],size[maxn];
int d[maxn][20],id[maxn][20],q[maxn];
vector<A>a[maxn],b[maxn][20];
bool vis[maxn]={false};
long long ans=0;
int n,Q,m,w[maxn],x,y,z,l,r;
int main(){
	freopen("shop_hnoi2015.in","r",stdin);
	freopen("shop_hnoi2015.out","w",stdout);
	scanf("%d%d%d",&n,&Q,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		W[x].push_back(z);
		G[y].push_back(x);
		W[y].push_back(z);
	}
	build(1,0,n,0);
	while(Q--){
		scanf("%d%d%d",&x,&l,&r);
		l=(l+(ans%m))%m;
		r=(r+(ans%m))%m;
		if(l>r)swap(l,r);
		printf("%lld\n",ans=query(x,l,r));
	}
	return 0;
}
void build(int x,int k,int s,int pr){//printf("build(%d,%d,%d,%d)\n",x,k,s,pr);
	x=getcenter(x,s);
	vis[x]=true;
	depth[x]=k;
	p[x]=pr;
	a[x].push_back(A(1<<31,0));
	a[x].push_back(A(w[x],0));
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
		p[G[x][i]]=x;
		d[G[x][i]][k]=W[x][i];
		b[G[x][i]][k].push_back(A(1<<31,0));
		getdis(G[x][i],k);
		sort(b[G[x][i]][k].begin(),b[G[x][i]][k].end());
		for(vector<A>::iterator it=b[G[x][i]][k].begin()+1;it!=b[G[x][i]][k].end();it++){
			a[x].push_back(*it);
			it->w+=(it-1)->w;
		}
	}
	sort(a[x].begin(),a[x].end());
	//printf("a[%d]:",x);for(vector<A>::iterator it=a[x].begin()+1;it!=a[x].end();it++)printf(" (%d,%I64d)",it->d,it->w);printf("\n");
	for(int i=1;i<=s;i++)a[x][i].w+=a[x][i-1].w;
	for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])build(G[x][i],k+1,size[G[x][i]],x);
}
int getcenter(int x,int s){
	int head=0,tail=0;
	q[tail++]=x;
	while(head!=tail){
		x=q[head++];
		size[x]=1;
		for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
			p[G[x][i]]=x;
			q[tail++]=G[x][i];
		}
	}
	for(int i=tail-1;i;i--)size[p[q[i]]]+=size[q[i]];
	x=q[0];
	for(;;){
		bool ok=true;
		for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]&&(size[G[x][i]]<<1)>s){
			x=G[x][i];
			ok=false;
			break;
		}
		if(ok)break;
	}
	return x;
}
void getdis(int x,int k){//printf("getdis(%d,%d)\n",x,k);
	int head=0,tail=0;
	q[tail++]=x;
	while(head!=tail){
		x=q[head++];
		id[x][k]=q[0];
		b[q[0]][k].push_back(A(w[x],d[x][k]));
		size[x]=1;//printf("%d ",x);
		for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
			p[G[x][i]]=x;
			d[G[x][i]][k]=d[x][k]+W[x][i];
			q[tail++]=G[x][i];
		}
	}//printf("\n");
	for(int i=tail-1;i;i--)size[p[q[i]]]+=size[q[i]];
}
long long query(int x,int l,int r){//printf("query(%d,%d,%d)\n",x,l,r);
	long long ans=(upper_bound(a[x].begin(),a[x].end(),A(r,0))-1)->w-(lower_bound(a[x].begin(),a[x].end(),A(l,0))-1)->w;
	for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){//printf("u=%d k=%d id[x][k]=%d\n",u,k,id[x][k]);
		vector<A>::iterator itl=lower_bound(a[u].begin(),a[u].end(),A(l,0))-1,itr=upper_bound(a[u].begin(),a[u].end(),A(r,0))-1;
		ans+=itr->w-itl->w+(itr-itl)*(long long)d[x][k];//printf("itr->w=%d itl->w=%d\n",(int)itr->w,(int)itl->w);
		itl=lower_bound(b[id[x][k]][k].begin(),b[id[x][k]][k].end(),A(l,0))-1;
		itr=upper_bound(b[id[x][k]][k].begin(),b[id[x][k]][k].end(),A(r,0))-1;
		ans-=itr->w-itl->w+(itr-itl)*(long long)d[x][k];//printf("OK\n");
	}
	return ans;
}