「前言」为防止在某巨巨的毒瘤idea 紫荆花之“店" 面前一脸懵，特滚来补此题。 我还是太naive了。
「题义」给出一棵单点度数很小的无根带边权、点权的树，每次询问在所有点权在[l,r]的点到c的距离之和。
「分析」考虑建立点分树，分治结构每个点都储存对应分治范围（简称范围）内的信息，询问时从c向后跳分治链，并逐级将信息合并得到整棵树的答案。
对于链上某一点x，设前一个点为px，显然我们需要用到的，x范围中（除去px范围）的所有合法的点（即点权在[l,r]内的点）到c的距离之和，拆开为这些点到x的距离和+这些点的个数乘以x到c的距离。对于第一部分我们将它看作x范围内所有点到x的距离和-px范围内所有点到x的距离和，第二部分同理。
这样，我们只需要对每个节点x储存范围内所有点点权age、到x的距离dis以及到上一级分治中心fa[x]的距离ldis（放在集合d[x]）。然后将d[x]按照age排序，那么x的分治范围对于查询中心c的产生贡的点献处于d[x]的一段区间上。利用前（后）缀和+二分就能地很好处理了。
#include <bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=150010;
const int inf=0x3f3f3f3f;
int n,Q,A,age[N];
int head[N],to[N<<1],last[N<<1],len[N<<1];
IL void addEdge(int x,int y,int w) {
static int cnt=0;
to[++cnt]=y,len[cnt]=w,last[cnt]=head[x],head[x]=cnt;
to[++cnt]=x,len[cnt]=w,last[cnt]=head[y],head[y]=cnt;
}
namespace dbl {
int fa[N][20],dep[N];
LL ds[N][20];
void prDfs(int x,int d) {
dep[x]=dep[fa[x][0]=d]+1;
for(int i=1; (1<<i)<=dep[x]; ++i) {
fa[x][i]=fa[fa[x][i-1]][i-1];
ds[x][i]=ds[fa[x][i-1]][i-1]+ds[x][i-1];
}
for(int i=head[x]; i; i=last[i]) {
if(to[i]!=d) ds[to[i]][0]=len[i],prDfs(to[i],x);
}
}
IL LL gtDis(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
LL ret=0; int dif=dep[x]-dep[y];
for(int i=19; ~i; --i) if((dif>>i)&1)
ret+=ds[x][i],x=fa[x][i];
if(x==y) return ret;
for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i])
ret+=ds[x][i],x=fa[x][i],ret+=ds[y][i],y=fa[y][i];
return ret+ds[x][0]+ds[y][0];
}
}
namespace dpd {
struct node {
LL dis,ldis; int age;
IL node(LL d=0,LL ld=0,int a=0):dis(d),ldis(ld),age(a){}
IL bool operator<(const node&d) const {
return age<d.age;
}
};
vector<node> d[N];
int root,siz[N],fa[N];
bool ban[N];
void prSiz(int x,int d) {
siz[x]=1;
for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d)
prSiz(to[i],x),siz[x]+=siz[to[i]];
}
void gtRoot(int x,int d,int t) {
static int f[N]={inf}; f[x]=siz[t]-siz[x];
for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d)
gtRoot(to[i],x,t),f[x]=max(f[x],siz[to[i]]);
if(f[x]<f[root]) root=x;
}
void prNode(int x,int d,LL dis) {
dpd::d[root].push_back(node(dis,dbl::gtDis(x,fa[root]),age[x]));
for(int i=head[x]; i; i=last[i]) {
if(!ban[to[i]]&&to[i]!=d) prNode(to[i],x,dis+len[i]);
}
}
void build(int x,int lrt) {
root=0; prSiz(x,0); gtRoot(x,0,x);
x=root; fa[x]=lrt; ban[x]=1; prNode(x,0,0);
sort(d[x].begin(),d[x].end());
d[x].push_back(node(0,0,A));
for(unsigned i=d[x].size()-2; ~i; --i) {
d[x][i].dis+=d[x][i+1].dis;
d[x][i].ldis+=d[x][i+1].ldis;
}
for(int i=head[x]; i; i=last[i]) {
if(!ban[to[i]]) build(to[i],x);
}
}
IL LL query(int c,int l,int r) {
vector<node>::iterator L,R; LL ans=0;
for(int x=c; x; x=fa[x]) {
L=lower_bound(d[x].begin(),d[x].end(),node(0,0,l));
R=upper_bound(d[x].begin(),d[x].end(),node(0,0,r));
ans+=dbl::gtDis(x,c)*(R-L)+(L->dis-R->dis);
if(fa[x]) ans-=dbl::gtDis(fa[x],c)*(R-L)+(L->ldis-R->ldis);
}
return ans;
}
}
int main() {
scanf("%d%d%d",&n,&Q,&A);
for(int i=1; i<=n; ++i) scanf("%d",&age[i]);
for(int x,y,w,i=n; --i; ) {
scanf("%d%d%d",&x,&y,&w);
addEdge(x,y,w);
}
dbl::prDfs(1,0);
dpd::build(1,0);
LL lans=0;
for(int u,a,b; Q--; ) {
scanf("%d%d%d",&u,&a,&b);
a=(lans+a)%A, b=(lans+b)%A; if(a>b) swap(a,b);
printf("%lld
",lans=dpd::query(u,a,b));
}
return 0;
} // 代码O2需要
好了，滚去看 紫荆花之恋 了