T 死了，合理怀疑是哪里复杂度写假了

大体思路是树剖求 lca 加 fhq 加淀粉树

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <random>

#define N 150001

using namespace std;
int n,q,A,tn,a[N],b[N];

int cnt,head[N];
struct Node { int to,nxt,dis; }e[N<<8];

void add(int u,int v,int w) { e[++cnt]=Node{v,head[u],w},head[u]=cnt; }

int siz[N],son[N],fa[N],top[N],dep[N];
long long dis[N];

void dfs1(int u,int Fa) {
    siz[u]=1,dep[u]=dep[fa[u]=Fa]+1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (v==Fa) continue;
        dis[v]=dis[u]+e[i].dis;
        dfs1(v,u);
        siz[u]+=siz[v];
        if (siz[v]>siz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int Top) {
    top[u]=Top;
    if (son[u]) dfs2(son[u],Top);
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (v==fa[u] or v==son[u]) continue;
        dfs2(v,v);
    }
}

int LCA(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

int tcnt,Rt[N][2];
struct Tree { long long val,sum; int key,siz,w,ls,rs; }t[N<<5];

void upd(int x) { t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+t[x].val,t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1; }

void merge(int &rt,int x,int y) {
    if (!x or !y) return rt=x+y,void();
    if (t[x].key<=t[y].key) rt=x,merge(t[rt].rs,t[x].rs,y);
    else rt=y,merge(t[rt].ls,x,t[y].ls);
    upd(rt);
}

void split(int rt,int &x,int &y,int k) {
    if (!rt) return x=y=0,void();
    if (t[rt].w<=k) x=rt,split(t[rt].rs,t[x].rs,y,k),upd(x);
    else y=rt,split(t[rt].ls,x,t[y].ls,k),upd(y);
}

void ins(int &rt,int val,int w) {
    int x=0,y=0,z=0;
    split(rt,x,y,w);
    t[z=++tcnt]=Tree{val,val,rand(),1,w,0,0};
    merge(x,x,z); merge(rt,x,y);
}

long long qry(int rt,int l,int r,long long k) {
    if (!rt) return 0;
    int x=0,y=0,z=0;
    split(rt,x,y,l-1); split(y,y,z,r);
    long long res=t[y].sum+k*t[y].siz;
    merge(y,y,z); merge(rt,x,y);
    return res;
}

int rt,S,_siz[N],_fa[N],msz[N],vis[N];

void find_rt(int u,int las) {
    _siz[u]=1,msz[u]=0;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (vis[v] or v==las) continue;
        find_rt(v,u);
        _siz[u]+=_siz[v],msz[u]=max(msz[u],_siz[v]);
    }
    msz[u]=max(msz[u],S-_siz[u]);
    if (msz[u]<msz[rt]) rt=u;
}

void dfs(int u) {
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (vis[v]) continue;
        int tS=S;
        S=_siz[v]>_siz[u]?S-_siz[u]:_siz[v],rt=0;
        find_rt(v,0); vis[rt]=1,_fa[rt]=u;
        dfs(rt);
        S=tS;
    }
}

void upd(int x,int k) {
    int u=x,v=_fa[x];
    while (u) {
        long long d=dis[x]+dis[u]-2*dis[LCA(x,u)];
        ins(Rt[u][0],d,k);
        if (v) {
            d=dis[x]+dis[v]-2*dis[LCA(x,v)];
            ins(Rt[u][1],d,k);
        }
        u=v,v=_fa[v];
    }
}

long long ask(int x,int l,int r) {
    int u=x,v=0; long long res=0;
    while (u) {
        long long d=dis[x]+dis[u]-2*dis[LCA(x,u)];
        res+=qry(Rt[u][0],l,r,d);
        if (v) res-=qry(Rt[v][1],l,r,d);
        // printf("%d:%lld\n",u,res);
        v=u,u=_fa[u];
    }
    return res;
}

signed main() {
    srand(388651);
    cin>>n>>q>>A;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1); tn=unique(b+1,b+n+1)-b-1;
    for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tn+1,a[i])-b;
    for (int i=1,u,v,w;i<n;i++) {
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    msz[rt=0]=1e9,S=n;
    find_rt(1,0); vis[rt]=1;
    dfs(rt);
    dfs1(1,0); dfs2(1,1);
    for (int i=1;i<=n;i++) upd(i,a[i]);
    long long las=0;
    for (int i=1,u,a0,b0;i<=q;i++) {
        cin>>u>>a0>>b0;
        int L=min((a0+las)%A,(b0+las)%A),R=max((a0+las)%A,(b0+las)%A);
        L=lower_bound(b+1,b+tn+1,L)-b;
        R=upper_bound(b+1,b+tn+1,R)-b-1;
        cout<<(las=ask(u,L,R))<<'\n';
    }
    return 0;
}