记录编号	613895	评测结果	AAAAAAAAAA
题目名称	1960.[HNOI 2015]开店	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	11.087 s
提交时间	2026-04-01 18:04:34	内存使用	79.56 MiB

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,q,A,rt,siz[N],mx[N],t[N],fa[N],vis[N];
vector<pair<int,int>>G[N];
int dfn[N],cnt,f[N],logn[N],st[N][21];
ll de[N];int deep[N];
void dfslca(int x,int par){
	dfn[x]=++cnt;deep[x]=deep[par]+1;
	st[dfn[x]][0]=x,f[x]=par;
	for(auto [y,z]:G[x]){
		if(y==f[x])continue;
		de[y]=de[x]+z;
		dfslca(y,x);
	}
	return;
}
#define cmp(a,b) (deep[a]<deep[b]?a:b)
int LCA(int a,int b){
	if(a==b)return a;
	if((a=dfn[a])>(b=dfn[b]))swap(a,b);
	a++;int d=logn[b-a+1];
	return f[cmp(st[a][d],st[b-(1<<d)+1][d])];
}
void init(){
	logn[0]=-1;
	for(int i=1;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=cmp(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	return;
}
ll dis(int a,int b){
	int c=LCA(a,b);
	return de[a]+de[b]-2*de[c];
}
struct DS{
	vector<int>p;
	int len,L,R;
	vector<ll>sum[2];
	void ins(int x){
		p.push_back(x);
		len++;
	}
	void init(int pos){
		sort(p.begin(),p.end(),[&](int u,int v){
			return t[u]<t[v];
		});
		sum[0].resize(len);
		for(int i=0;i<len;i++){
			sum[0][i]=dis(p[i],pos);
			if(i)sum[0][i]+=sum[0][i-1];
		}
		if(fa[pos]){
			sum[1].resize(len);
			for(int i=0;i<len;i++){
				sum[1][i]=dis(p[i],fa[pos]);
				if(i)sum[1][i]+=sum[1][i-1];
			}
		}
		for(int i=0;i<len;i++)p[i]=t[p[i]];
		return;
	}
	ll ask(int l,int r,int o,ll &cnt){
		if(!len)return cnt=0;
		L=lower_bound(p.begin(),p.end(),l)-p.begin();
		R=upper_bound(p.begin(),p.end(),r)-p.begin()-1;
		if(R<0)return cnt=0;
		cnt=R-L+1;return sum[o][R]-(L?sum[o][L-1]:0); 
	}
}tr[N];
void add(int x,int y,int z){
	G[x].push_back(mp(y,z));
}
void DFS(int x,int par,int tp){
	tr[tp].ins(x);
	for(auto [y,z]:G[x]){
		if(y==par||vis[y])continue;
		DFS(y,x,tp);
	}
	return;
}
void dfs(int x,int par,int sum){
	siz[x]=1,mx[x]=0;
	for(auto [y,z]:G[x]){
		if(y==par||vis[y])continue;
		dfs(y,x,sum);
		siz[x]+=siz[y];
		mx[x]=max(mx[x],siz[y]);
	}
	mx[x]=max(mx[x],sum-siz[x]);
	if(mx[x]<mx[rt])rt=x;
	return;
}
void solve(int u,int sum){
	vis[u]=1;
	tr[u].ins(u);
	for(auto [v,w]:G[u]){
		if(vis[v])continue;
		DFS(v,u,u);
	}
	for(auto [v,w]:G[u]){
		if(vis[v])continue;
		int sz=(siz[v]>siz[u]?sum-siz[u]:siz[v]);
		rt=0,dfs(v,u,sz);fa[rt]=u;
		solve(rt,sz);
	}
	tr[u].init(u);
	return;
}

int main(){
	freopen("shop_hnoi2015.in","r",stdin);
	freopen("shop_hnoi2015.out","w",stdout);
	scanf("%d %d %d",&n,&q,&A);
	for(int i=1;i<=n;i++)scanf("%d",t+i);
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	dfslca(1,0);
	init();
	mx[0]=1e9,rt=0;
	dfs(1,0,n);
	solve(rt,n);
	int u,l,r;
	ll ans=0,c1,c2;
	while(q--){
		scanf("%d %d %d",&u,&l,&r);
		l=(l+ans)%A,r=(r+ans)%A;
		if(l>r)swap(l,r);
		ans=tr[u].ask(l,r,0,c1);
		for(int v=u;fa[v];v=fa[v]){
			ans+=tr[fa[v]].ask(l,r,0,c1)-tr[v].ask(l,r,1,c2);
			ans+=(c1-c2)*dis(u,fa[v]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}