我们考虑一个暴力：若两点求题目中所需距离，那么选一个点到根的路径上所有点权+1。然后求另一个点到根的点权和即可。
然后？这个操作是可加的，可减的，因此可以具备前缀操作的性质。
把所有询问离线，然后链剖。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 100500 #define maxq 200500 #define maxe 100500 #define mod 201314 using namespace std; struct edge { long long v,nxt; }e[maxe]; struct aasskk { long long id,pos,r,sgn; }ask[maxq]; long long n,q,x,y,z,g[maxv],top[maxv],fath[maxv],son[maxv],dis[maxv],w[maxv],size[maxv]; long long ls[maxv<<2],rs[maxv<<2],value[maxv<<2],lazy[maxv<<2],nume=0,numq=0,cnt=0,tot=0; long long ans[maxq],root; bool cmp(aasskk x,aasskk y) { return x.pos<y.pos; } void addedge(long long u,long long v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void addask(long long id,long long pos,long long r,long long sgn) { ask[++numq].id=id; ask[numq].pos=pos; ask[numq].r=r; ask[numq].sgn=sgn; } void dfs1(long long x) { size[x]=1;son[x]=0; for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if (v!=fath[x]) { fath[v]=x;dis[v]=dis[x]+1; dfs1(v); size[x]=size[x]+size[v]; if (size[v]>size[son[x]]) son[x]=v; } } } void dfs2(long long x,long long father) { w[x]=++cnt;top[x]=father; if (son[x]!=0) dfs2(son[x],father); for (long long i=g[x];i;i=e[i].nxt) { long long v=e[i].v; if ((v!=fath[x]) && (v!=son[x])) dfs2(v,v); } } void build(long long &now,long long left,long long right) { now=++tot; value[now]=0;lazy[now]=0; if (left==right) return; long long mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void pushdown(long long now,long long left,long long right) { if (lazy[now]!=0) { long long mid=(left+right)>>1; lazy[ls[now]]+=lazy[now]; lazy[rs[now]]+=lazy[now]; value[ls[now]]+=(mid-left+1)*lazy[now]; value[rs[now]]+=(right-mid)*lazy[now]; lazy[now]=0; } } void big_modify(long long now,long long left,long long right,long long l,long long r) { pushdown(now,left,right); if ((left==l) && (right==r)) { lazy[now]+=1; value[now]+=(right-left+1); return; } long long mid=(left+right)>>1; if (r<=mid) big_modify(ls[now],left,mid,l,r); else if (l>=mid+1) big_modify(rs[now],mid+1,right,l,r); else { big_modify(ls[now],left,mid,l,mid); big_modify(rs[now],mid+1,right,mid+1,r); } value[now]=value[ls[now]]+value[rs[now]]; } long long query(long long now,long long left,long long right,long long l,long long r) { pushdown(now,left,right); if ((left==l) && (right==r)) return value[now]; long long mid=(left+right)>>1; if (r<=mid) return query(ls[now],left,mid,l,r); else if (l>=mid+1) return query(rs[now],mid+1,right,l,r); else return query(ls[now],left,mid,l,mid)+query(rs[now],mid+1,right,mid+1,r); } void work1(long long x) { long long f1=top[x]; while (f1!=1) { big_modify(root,1,cnt,w[f1],w[x]); x=fath[f1];f1=top[x]; } big_modify(root,1,cnt,w[1],w[x]); } void work2(long long x) { long long r=ask[x].r,ret=0; long long f1=top[r]; while (f1!=1) { ret=(ret+query(root,1,cnt,w[f1],w[r]))%mod; r=fath[f1];f1=top[r]; } ret=(ret+query(root,1,cnt,w[1],w[r]))%mod; ans[ask[x].id]=(ans[ask[x].id]+ret*ask[x].sgn)%mod; ans[ask[x].id]=(ans[ask[x].id]+mod)%mod; } int main() { scanf("%lld%lld",&n,&q); for (long long i=1;i<=n-1;i++) { scanf("%lld",&x); addedge(x+1,i+1); addedge(i+1,x+1); } for (long long i=1;i<=q;i++) { scanf("%lld%lld%lld",&x,&y,&z); if (x!=0) addask(i,x,z+1,-1); addask(i,y+1,z+1,1); } sort(ask+1,ask+numq+1,cmp); dfs1(1); dfs2(1,1); build(root,1,cnt); long long now=1; for (long long i=1;i<=n;i++) { work1(i); while (ask[now].pos==i) { work2(now); now++; } } for (long long i=1;i<=q;i++) { while (ans[i]<0) ans[i]=(ans[i]+mod)%mod; printf("%lld ",ans[i]%mod); } return 0; }