```cpp
#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
#define mk make_pair
using namespace std;
template<class T>void read(T &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
x*=f;
}
typedef long long ll;
const int MAXN=1.5e5+5,inf=0x3f3f3f3f;
int n,q,A,a[MAXN];
struct E{
int v,w,nxt;
} e[MAXN<<1];
int ecnt,h[MAXN];
void ade(int u,int v,int w){
e[++ecnt].v=v;
e[ecnt].w=w;
e[ecnt].nxt=h[u];
h[u]=ecnt;
}
int dep[MAXN],fa[MAXN],id[MAXN],dfn,stb[20][MAXN],lg[MAXN],dis[MAXN];
int get(int x,int y){
return (dep[x]<dep[y])?x:y;
}
int lca(int x,int y){
if(x==y)return x;
if((x=id[x])>(y=id[y]))swap(x,y);
int k=lg[y-x++];
return get(stb[k][x],stb[k][y-(1<<k)+1]);
}
int getdis(int x,int y){
return dis[x]+dis[y]-2ll*dis[lca(x,y)];
}
void dfs1(int u,int ff){
dep[u]=dep[ff]+1,fa[u]=ff;
id[u]=++dfn;
stb[0][id[u]]=ff;
int v;
for(int i=h[u];i;i=e[i].nxt){
v=e[i].v;
if(v==ff)continue;
dis[v]=dis[u]+e[i].w;
dfs1(v,u);
}
}
int sz[MAXN],mxp[MAXN],cent,vis[MAXN];
int dfa[MAXN];
vector<int> newt[MAXN];
void fdrt(int u,int ff,int sum){
sz[u]=1,mxp[u]=0;
int v;
for(int i=h[u];i;i=e[i].nxt){
v=e[i].v;
if(v==ff||vis[v])continue;
fdrt(v,u,sum);
sz[u]+=sz[v];
mxp[u]=max(mxp[u],sz[v]);
}
mxp[u]=max(mxp[u],sum-mxp[u]);
if(mxp[u]<mxp[cent])cent=u;
}
void fenzhi(int u,int sum){
vis[u]=1;
int v;
for(int i=h[u];i;i=e[i].nxt){
v=e[i].v;
if(vis[v])continue;
cent=0;
int tt=(sz[v]<sz[u])?sz[u]:(sum-sz[u]);
fdrt(v,u,tt);
dfa[cent]=u;
newt[u].pb(cent);
fenzhi(cent,tt);
}
}
struct nd{
int w;
ll d,sum;
bool operator<(const nd&t)const{
return w<t.w;
}
};
vector<nd> tr[MAXN];
void build(int x){
int u=x;
while(u){
tr[u].push_back((nd){a[x],getdis(u,x),0});
u=dfa[u];
}
}
//1:sum of dis,2:cnt
pair<ll,int> fd(int u,int l,int r){
int nl=0,nr=tr[u].size(),mid,ansl=-1,ansr=-1;
nr--;
while(nl<=nr){
mid=(nl+nr)>>1;
if(tr[u][mid].w<=r)ansr=mid,nl=mid+1;
else nr=mid-1;
}
if(ansr==-1){
//cout<<"err1 "<<u<<' '<<l<<' '<<r<<endl;
return mk(0,0);
}
nl=0,nr=tr[u].size();
nr--;
while(nl<=nr){
mid=(nl+nr)>>1;
if(tr[u][mid].w>=l)ansl=mid,nr=mid-1;
else nl=mid+1;
}
if(ansl==-1){
//cout<<"err2 "<<u<<' '<<l<<' '<<r<<endl;
return mk(0,0);
}
if(ansr<ansl){
//cout<<"err3 "<<u<<' '<<l<<' '<<r<<endl;
//cout<<ansl<<' '<<ansr<<endl;
return mk(0,0);
}
ll pre=(ansl==0)?0:(tr[u][ansl-1].sum);
return mk(tr[u][ansr].sum-pre,ansr-ansl+1);
}
ll quychn(int x,int l,int r){
int u=dfa[x],pre=x;
pair<ll,int> tmp;
tmp=fd(x,l,r);
ll res=tmp.first;
//cout<<"xx "<<x<<' '<<x<<' '<<tmp.first<<' '<<tmp.second<<endl;
while(u){
for(int v:newt[u]){
if(v==pre)continue;
int d1=getdis(u,x),d2=getdis(u,v);
tmp=fd(v,l,r);
//cout<<"xx "<<u<<' '<<v<<' '<<tmp.first<<' '<<tmp.second<<endl;
res+=tmp.first+1ll*tmp.second*(d1+d2);
}
if(l<=a[u]&&a[u]<=r){
res+=getdis(u,x);
//cout<<"xx "<<u<<' '<<getdis(u,x)<<endl;
}
pre=u,u=dfa[u];
}
return res;
}
int main(){
// freopen("shop1.in","r",stdin);
// freopen("tt.out","w",stdout);
read(n),read(q),read(A);
rep(i,1,n)read(a[i]);
int u,v,w;
rep(i,1,n-1){
read(u),read(v),read(w);
ade(u,v,w),ade(v,u,w);
}
dfs1(1,0);
rep(i,2,n)lg[i]=lg[i>>1]+1;
rep(j,1,lg[n])
for(int i=1;i+(1<<j)-1<=n;i++)
stb[j][i]=get(stb[j-1][i],stb[j-1][i+(1<<(j-1))]);
mxp[cent=0]=inf;
fdrt(1,0,n);
fdrt(cent,0,n);
fenzhi(cent,n);
rep(i,1,n)build(i);
rep(i,1,n){
sort(tr[i].begin(),tr[i].end());
ll pre=0;
int tsz=tr[i].size();
rep(j,0,tsz-1){
tr[i][j].sum=pre+tr[i][j].d;
pre+=tr[i][j].d;
}
}
int l,r;
ll lst=0,ta,tb;
while(q--){
read(u),read(ta),read(tb);
ta=(ta%A+lst%A)%A,tb=(tb%A+lst%A)%A;
l=min(ta,tb),r=max(ta,tb);
//cout<<"real "<<u<<' '<<l<<' '<<r<<endl;
printf("%lld\n",lst=quychn(u,l,r));
}
return 0;
}
/*
10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4
*/
```
by lao_li @ 2023-02-23 21:35:18
Wa 不清楚，没有仔细看代码，可能是哪里写挂了
但是您这样询问复杂度是不对的，考虑初始图是一个菊花图，然后第一次点分治重心选中间的点，那么询问一个点就要把重心的所有儿子都遍历一遍，就卡成 $O(n)$ 了
还是建议每个点维护两个 $vector$ ，一个维护自己的，一个维护父亲的，维护信息类似点分树模板那样
希望对你有帮助
by wenqizhi1125 @ 2023-02-23 21:43:49
@[lao_li](/user/317650)
by wenqizhi1125 @ 2023-02-23 21:45:24
@[wenqizhi1125](/user/632453) 这题限制了度$<3$吧？
by lao_li @ 2023-02-23 21:49:35
$\leq 3$
by lao_li @ 2023-02-23 21:49:53
@[lao_li](/user/317650)
那确实是，我的错，没有仔细看题
by wenqizhi1125 @ 2023-02-23 21:52:52