```cpp
#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
const LL N=200010,M=2000010,INF=0x3f3f3f3f;
inline LL max(LL x,LL y){return x>y?x:y;}
inline LL min(LL x,LL y){return x<y?x:y;}
inline void swap(LL &x,LL &y){x^=y^=x^=y;}
LL head[N],ver[M],edge[M],Next[M],tot;
LL n,m,t,rt,lastans,d[N],f[N],val[N],vis[N],dist[N],size[N];
LL in[N],out[N],st[N<<2][20],lg[N<<2],ts;
struct node{LL pos,sum;};
bool operator <(node a,node b){
return a.pos<b.pos;
}
vector<node> v[2][N];//0 -> dis(itself);1 -> dis(fa)
void upd(LL u,LL op,LL pos,LL dis){
v[op][u].push_back((node){pos,dis});
}
LL ask(LL u,LL op,LL l,LL r,LL &fi,LL &se){
fi=lower_bound(v[op][u].begin(),v[op][u].end(),(node){l,0})-v[op][u].begin();
se=upper_bound(v[op][u].begin(),v[op][u].end(),(node){r,0})-v[op][u].begin();
return v[op][u][fi].sum-v[op][u][se].sum;
}
void add(LL x,LL y,LL z){
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void dfs(LL x,LL fa){
d[x]=d[fa]+1;
in[x]=++ts,st[ts][0]=x;
for(LL i=head[x];i;i=Next[i]){
LL y=ver[i],z=edge[i];
if(y==fa)continue;
dist[y]=dist[x]+z;
dfs(y,x);
}
out[x]=++ts;
if(fa)st[ts][0]=fa;
}
void init(){
for(LL i=2;i<=N<<1;i++)lg[i]=lg[i>>1]+1;
for(LL j=1;(1<<j)<=ts;j++)
for(LL i=1;i+(1<<j)-1<=ts;i++){
LL x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
st[i][j]=(d[x]<d[y])?x:y;
}
}
LL lca(LL x,LL y){
LL l=in[x],r=in[y];
if(l>r)swap(l,r);LL Lg=lg[r-l+1];
return d[st[l][Lg]]<d[st[r-(1<<Lg)+1][Lg]]?st[l][Lg]:st[r-(1<<Lg)+1][Lg];
}
LL get(LL x,LL y){
return dist[x]+dist[y]-2*dist[lca(x,y)];
}
void get_size(LL x,LL fa){
size[x]=1;
for(LL i=head[x];i;i=Next[i]){
LL y=ver[i];
if(y==fa||vis[y])continue;
get_size(y,x);
size[x]+=size[y];
}
}
void get_rt(LL x,LL fa,LL sum){
size[x]=1;
LL flag=1;
for(LL i=head[x];i;i=Next[i]){
LL y=ver[i];
if(y==fa||vis[y])continue;
get_rt(y,x,sum);
size[x]+=size[y];
if(size[y]>sum/2)flag=0;
}
if(flag&&sum-size[x]<=sum/2)rt=x;
}
void get_dis(LL x,LL fa,LL op,LL dis){
upd(rt,op,val[x],dis);
for(LL i=head[x];i;i=Next[i]){
LL y=ver[i],z=edge[i];
if(y==fa||vis[y])continue;
get_dis(y,x,op,dis+z);
}
}
void solve(LL x){
vis[x]=1;
get_dis(x,0,0,0);
for(LL i=head[x];i;i=Next[i]){
LL y=ver[i],z=edge[i];
if(vis[y])continue;
get_size(y,x);
get_rt(y,x,size[y]);
f[rt]=x;
get_dis(y,x,1,z);
solve(rt);
}
upd(x,0,INF,0);
upd(x,1,INF,0);
sort(v[0][x].begin(),v[0][x].end());
sort(v[1][x].begin(),v[1][x].end());
for(LL i=v[0][x].size();i;i--)
v[0][x][i-1].sum+=v[0][x][i].sum;
for(LL i=v[1][x].size();i;i--)
v[1][x][i-1].sum+=v[1][x][i].sum;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&t);
for(LL i=1;i<=n;i++)
scanf("%lld",&val[i]);
for(LL i=1;i<n;i++){
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dfs(1,0);
init();
get_rt(1,0,n);
solve(rt);
while(m--){
LL x,a,b,l,r,fi,se;
scanf("%lld%lld%lld",&x,&a,&b);
l=(a+lastans)%t;
r=(b+lastans)%t;
if(l>r)swap(l,r);
lastans=0;
lastans+=ask(x,0,l,r,fi,se);
for(LL i=x;f[i];i=f[i]){
LL len=get(x,f[i]);
lastans+=ask(f[i],0,l,r,fi,se);
lastans+=len*(se-fi);
lastans-=ask(i,1,l,r,fi,se);
lastans-=len*(se-fi);
}
printf("%lld\n",lastans);
}
return 0;
}
```
by Diaоsi @ 2021-08-10 10:40:07
开 ```-O2```可过,不知道HNOI2015有没有开放 ```-O2``` /yun
by Diaоsi @ 2021-08-10 10:42:15
@[Diaоsi](/user/137242) $O(n \log^2 n)$ 好像不开O2是过不了
by ArchaioMeles @ 2021-08-10 11:03:19
能不开long long 就别开吧
by ATZdhjeb @ 2021-08-10 11:07:42
@[ATZdhjeb](/user/483317) 涉及到要开 ```long long``` 的变量很多啊,不想一个一个开了
by Diaоsi @ 2021-08-10 11:18:26
@[十里](/user/526711) 我的不开O2也可以过 , 但是最慢的点到了 $\geq 5.7s$
by zyc2003 @ 2021-08-10 12:49:44