见代码

#include<its/stdc++.h>
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e6+5,INF=1e9;
int n,m,q;
int a[N];
int cnt,top,st[N*2];
tuple<int,int,int>A[N];
tuple<int,int,LL>ans[N];
vector<tuple<int,int,int,int>>Q[N];
int f[N],Gh[N],Gnxt[N],sz[N],d[N],Top[N],son[N];
struct node{
    int ls,rs,mx,mn,sz,mnp;
    pair<int,int>L;
    pair<int,int>R;
    pair<LL,LL>S;
    node(){}
    node(pair<int,int>l,pair<int,int>r,int v){
        ls=0,rs=0,sz=1;
        mnp=l.first<=r.first?INF:(r.second-l.second+1);
        L=l,R=r,mx=mn=v;
        S=make_pair(1ll*v*(R.first-L.first),1ll*v*(R.second-L.second+1));
    }
    node(pair<int,int>l,pair<int,int>r,int _mx,int _mn,pair<LL,LL>s,int _ls,int _rs,int _sz,int _mnp){
        ls=_ls,rs=_rs,mx=_mx,mn=_mn,sz=_sz,mnp=_mnp,L=l,R=r,S=s;
    }
}T[N*2];
inline int merge(int x,int y){
    if(!x||!y)return x+y;
    int z=0;
    const int xsz=T[x].sz,ysz=T[y].sz;
    if(min(xsz,ysz)*7>=(xsz+ysz)*2){
        z=top?st[top--]:++cnt;
        T[z]=node(T[x].L,T[y].R,
            max(T[x].mx,T[y].mx),
            min(T[x].mn,T[y].mn),
            make_pair(T[x].S.first+T[y].S.first,T[x].S.second+T[y].S.second),
            x,y,xsz+ysz,min(T[x].mnp,T[y].mnp));
    }
    else{
        const int xls=T[x].ls,xrs=T[x].rs,yls=T[y].ls,yrs=T[y].rs;
        if(xsz>ysz){
            if(T[xls].sz*7>=(xsz+ysz)*2)st[++top]=x,z=merge(xls,merge(xrs,y));
            else{
                st[++top]=x,st[++top]=xrs;
                const int xrls=T[xrs].ls,xrrs=T[xrs].rs;
                z=merge(merge(xls,xrls),merge(xrrs,y));
            }
        }
        else{
            if(T[yrs].sz*7>=(xsz+ysz)*2)st[++top]=y,z=merge(merge(x,yls),yrs);
            else{
                st[++top]=y,st[++top]=yls;
                const int ylls=T[yls].ls,ylrs=T[yls].rs;
                z=merge(merge(x,ylls),merge(ylrs,yrs));
            }
        }
    }
    return z;
}
inline void split(int x,int t,int k,int&p,int&q){
    const int l=T[x].L.first*t+T[x].L.second;
    const int r=T[x].R.first*t+T[x].R.second;
    if(k<l)return p=0,q=x,void();
    if(r<=k)return p=x,q=0,void();
    if(!T[x].ls){
        int y=top?st[top--]:++cnt;
        T[q=y]=node(make_pair(0,k+1),T[x].R,T[x].mn);
        T[p=x]=node(T[x].L,make_pair(0,k),T[x].mn);
        return;
    }
    const int xls=T[x].ls,xrs=T[x].rs;st[++top]=x;
    if(k<=T[xls].R.first*t+T[xls].R.second)split(xls,t,k,p,q),q=merge(q,xrs);
    else split(xrs,t,k,p,q),p=merge(xls,p);
}
inline void qry(int x,int L,int R,int t,tuple<int,int,LL>&ans){
    const int l=T[x].L.first*t+T[x].L.second;
    const int r=T[x].R.first*t+T[x].R.second;
    if(R<l||r<L)return;
    if(L<=l&&r<=R){
        get<0>(ans)=min(get<0>(ans),T[x].mn);
        get<1>(ans)=max(get<1>(ans),T[x].mx);
        get<2>(ans)+=1ll*T[x].S.first*t+T[x].S.second;
        return;
    }
    if(!T[x].ls){
        get<0>(ans)=min(get<0>(ans),T[x].mn);
        get<1>(ans)=max(get<1>(ans),T[x].mx);
        get<2>(ans)+=T[x].mn*(min(R,r)-max(L,l)+1ll);
        return;
    }
    qry(T[x].ls,L,R,t,ans),qry(T[x].rs,L,R,t,ans);
}
inline void upd(int&rt){
    const int t=T[rt].mnp-1;
    int u=rt,v;
    for(;T[u].ls;)
        if(T[T[u].ls].mnp==t+1)u=T[u].ls;
        else u=T[u].rs;
    const int k=T[u].L.first*t+T[u].L.second;
    int p,q;split(rt,t,k-1,p,q),split(q,t,k,rt,q);
    st[++top]=rt;
    if(p&&q){
        int u=p,v=q;
        vector<int>stu,stv;
        for(;T[u].rs;u=T[u].rs)stu.emplace_back(u);
        for(;T[v].ls;v=T[v].ls)stv.emplace_back(v);
        if(T[u].mn<=T[v].mn)
            T[u]=node(T[u].L,make_pair(-1,k+t),T[u].mn),
            T[v]=node(make_pair(-1,k+t+1),T[v].R,T[v].mn);
        else
            T[u]=node(T[u].L,make_pair(0,k-1),T[u].mn),
            T[v]=node(make_pair(0,k),T[v].R,T[v].mn);
        while(!stu.empty()){
            const auto z=stu.back(),x=T[z].ls,y=T[z].rs;
            T[z]=node(T[x].L,T[y].R,
                max(T[x].mx,T[y].mx),
                min(T[x].mn,T[y].mn),
                make_pair(T[x].S.first+T[y].S.first,T[x].S.second+T[y].S.second),
                x,y,T[x].sz+T[y].sz,min(T[x].mnp,T[y].mnp));
            stu.pop_back();
        }
        while(!stv.empty()){
            const auto z=stv.back(),x=T[z].ls,y=T[z].rs;
            T[z]=node(T[x].L,T[y].R,
                max(T[x].mx,T[y].mx),
                min(T[x].mn,T[y].mn),
                make_pair(T[x].S.first+T[y].S.first,T[x].S.second+T[y].S.second),
                x,y,T[x].sz+T[y].sz,min(T[x].mnp,T[y].mnp));
            stv.pop_back();
        }
    }
    rt=merge(p,q);
}
inline void ins(int&rt,int k,int v,int t){
    int p,q;split(rt,t,k-1,p,q),split(q,t,k,rt,q);
    if(T[rt].mn<v){
        T[rt]=node(T[rt].L,T[rt].R,v);
        if(p){
            int u=p;
            vector<int>stu;
            for(;T[u].rs;u=T[u].rs)stu.emplace_back(u);
            if(T[u].mn<=T[rt].mn)
                T[u]=node(T[u].L,make_pair(-1,k+t-1),T[u].mn),
                T[rt]=node(make_pair(-1,k+t),T[rt].R,T[rt].mn);
            else
                T[u]=node(T[u].L,make_pair(0,k-1),T[u].mn),
                T[rt]=node(make_pair(0,k),T[rt].R,T[rt].mn);
            while(!stu.empty()){
                const auto z=stu.back(),x=T[z].ls,y=T[z].rs;
                T[z]=node(T[x].L,T[y].R,
                    max(T[x].mx,T[y].mx),
                    min(T[x].mn,T[y].mn),
                    make_pair(T[x].S.first+T[y].S.first,T[x].S.second+T[y].S.second),
                    x,y,T[x].sz+T[y].sz,min(T[x].mnp,T[y].mnp));
                stu.pop_back();
            }
        }
        if(q){
            int v=q;
            vector<int>stv;
            for(;T[v].ls;v=T[v].ls)stv.emplace_back(v);
            if(T[rt].mn<=T[v].mn)
                T[rt]=node(T[rt].L,make_pair(-1,k+t),T[rt].mn),
                T[v]=node(make_pair(-1,k+t+1),T[v].R,T[v].mn);
            else
                T[rt]=node(T[rt].L,make_pair(0,k),T[rt].mn),
                T[v]=node(make_pair(0,k+1),T[v].R,T[v].mn);
            while(!stv.empty()){
                const auto z=stv.back(),x=T[z].ls,y=T[z].rs;
                T[z]=node(T[x].L,T[y].R,
                    max(T[x].mx,T[y].mx),
                    min(T[x].mn,T[y].mn),
                    make_pair(T[x].S.first+T[y].S.first,T[x].S.second+T[y].S.second),
                    x,y,T[x].sz+T[y].sz,min(T[x].mnp,T[y].mnp));
                stv.pop_back();
            }
        }
    }
    rt=merge(merge(p,rt),q);
}
inline void dfs1(int u){
    sz[u]=1,son[u]=0;
    for(int v=Gh[u];v;v=Gnxt[v])
        d[v]=d[u]+1,dfs1(v),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
}
inline void dfs2(int u,int tp){
    Top[u]=tp;
    for(int v=Gh[u];v;v=Gnxt[v])
        dfs2(v,v==son[u]?tp:v);
}
inline void calc(int u,int pd,int t){
    if(a[u])A[++m]=make_tuple(t,pd,a[u]);
    for(int v=Gh[u];v;v=Gnxt[v])calc(v,pd,t+1);
}
inline void solve(int u){
    for(int p=u;p;p=son[p])
        for(int v=Gh[p];v;v=Gnxt[v])if(v!=son[p])solve(v);
    if(Q[u].empty())return;
    m=0,cnt=0,top=0;
    int len=-1;
    for(int p=u;p;p=son[p]){
        ++len;
        if(a[p])A[++m]=make_tuple(0,d[p]-d[u],a[p]);
        for(int v=Gh[p];v;v=Gnxt[v])if(v!=son[p])calc(v,d[p]-d[u],1);
    }
    sort(A+1,A+m+1),sort(Q[u].begin(),Q[u].end());
    int rt=++cnt,p=1;
    T[rt]=node(make_pair(0,0),make_pair(0,len),0);
    for(auto [t,l,r,id]:Q[u]){
        for(;p<=m&&get<0>(A[p])<=t;++p){
            const auto [nt,x,y]=A[p];
            while(T[rt].mnp<=nt)upd(rt);
            ins(rt,x,y,nt);
        }
        while(T[rt].mnp<=t)upd(rt);
        qry(rt,l,r,t,ans[id]);
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    read(n,q);
    for(int i=2;i<=n;++i)
        read(f[i]),Gnxt[i]=Gh[f[i]],Gh[f[i]]=i;
    for(int i=1;i<=n;++i)read(a[i]);
    dfs1(1),dfs2(1,1);
    for(int i=1;i<=q;++i){
        int x,y,t;read(x,y,t),ans[i]=make_tuple(n,0,0);
        for(;Top[x]!=Top[y];x=f[Top[x]]){
            if(d[Top[x]]<d[Top[y]])swap(x,y);
            Q[Top[x]].emplace_back(t,0,d[x]-d[Top[x]],i);
        }
        if(d[x]>d[y])swap(x,y);
        Q[Top[x]].emplace_back(t,d[x]-d[Top[x]],d[y]-d[Top[x]],i);
    }
    solve(1);
    for(int i=1;i<=q;++i)println(ans[i]);
    return 0;
}
                               ```