題面
考慮到詢問的\(l..r,z\)具有可減性，考慮把詢問差分掉，拆成\(r,z\)和\(l-1,z\)。
顯然這些LCA一定在\(z\)到根的路徑上。下面的問題就是怎么統計。
考慮不是那么暴力的暴力。
我們似乎可以把\(1..r\)的所有點先瞎搞一下，求出一個點內部有幾個\(1..r\)以內的點，記作\(w[i]\)。另假設\(fson[x]\)表示\(x\)的孩子中\(z\)這個點所在孩子
那么答案就是
\[ (\sum_{x\text{是$z$的祖先}} (w[x]-w[fson[x]])\cdot dep[x] ) + w[z]\cdot dep[z] \]
發現\(x\)有多少祖先，\(dep[x]\)就是幾。所以可以把\(w[x]-w[son[x]]\)放到其所有祖先上各統計一次。
這樣就發現，被減掉的\(w[fson[x]]?\)又會被后面的繼續加回來。
所以最終答案就是
\[ \sum_{x\text{是$z$的祖先}} w[x] \]
那么，如果維護這個\(w[x]\)呢？
從小到大循環\(1..n\)，（也就是循環的是詢問的差分后的那個\(r\)指針）然后只需要把\(i\)的祖先都更新一個\(1\)就可以了，然后枚舉掛在\(i\)上的詢問，統計從\(z\)到根的路徑和。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define REP(i,a,n) for(register int i(a);i<=(n);++i)
#define FEC(i,x,y) for(register int i=head[x],y=g[i].to;i;i=g[i].ne,y=g[i].to)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define lc o<<1
#define rc o<<1|1
const int SZ=(1<<21)+1;char ibuf[SZ],*iS,*iT,obuf[SZ],*oS=obuf,*oT=obuf+SZ-1;
#ifdef ONLINE_JUDGE
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,stdin),(iS==iT?EOF:*iS++)):*iS++)
#else
#define gc() getchar()
#endif
template<typename I>inline void read(I&x){char c=gc();int f=0;for(;c<'0'||c>'9';c=gc())c=='-'?f=1:0;for(x=0;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c&15);f?x=-x:0;}
inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
#define printf(...) (iS>iT&&(flush(),1),oS+=sprintf(oS,__VA_ARGS__))
template<typename A,typename B>inline char SMAX(A&a,const B&b){return a<b?a=b,1:0;}
template<typename A,typename B>inline char SMIN(A&a,const B&b){return a>b?a=b,1:0;}
typedef long long ll;const int N=50000+7,P=201314;
int n,m,x,y,z,ans[N];
int dep[N],f[N],num[N],son[N],top[N],dfn[N],pre[N],dfc;
struct Edge{int to,ne;}g[N];int head[N],tot;
inline void Addedge(int x,int y){g[++tot].to=y;g[tot].ne=head[x];head[x]=tot;}
struct Questions{int opt,r,z,*ans;inline char operator<(const Questions&a)const{return r<a.r;}}q[N<<1];inline int SMOD(int x){return x>=P?x-P:x;}
inline void SADD(int&x,const int&y){x+=y;x>=P?x-=P:0;}
inline void SDEL(int&x,const int&y){x-=y;x<0?x+=P:0;}
inline void DFS1(int x,int fa=0){dep[x]=dep[fa]+1;f[x]=fa;num[x]=1;FEC(i,x,y)if(y!=fa){DFS1(y,x);num[x]+=num[y];if(num[y]>num[son[x]])son[x]=y;}
}
inline void DFS2(int x,int pa){top[x]=pa;dfn[x]=++dfc;pre[dfc]=x;if(!son[x])return;DFS2(son[x],pa);FEC(i,x,y)if(y!=f[x]&&y!=son[x])DFS2(y,y);
}
struct Node{int sum,add;}t[N<<2];
inline void Add(int o,int L,int R,int l,int r){if(l<=L&&R<=r)return SADD(t[o].add,1),SADD(t[o].sum,R-L+1);int M=(L+R)>>1;if(l<=M)Add(lc,L,M,l,r);if(r>M)Add(rc,M+1,R,l,r);t[o].sum=SMOD(t[lc].sum+t[rc].sum);SADD(t[o].sum,t[o].add*(R-L+1)%P);//錯誤筆記：Pushup的時候要記得更新標記
}inline void Add(int l,int r){Add(1,1,n,l,r);}
inline int Sum(int o,int L,int R,int l,int r,int k=0){if(l<=L&&R<=r)return SMOD(t[o].sum+(ll)(R-L+1)*k%P);int M=(L+R)>>1;if(r<=M)return Sum(lc,L,M,l,r,SMOD(k+t[o].add));else if(l>M)return Sum(rc,M+1,R,l,r,SMOD(t[o].add+k));else return SMOD(Sum(lc,L,M,l,r,SMOD(k+t[o].add))+Sum(rc,M+1,R,l,r,SMOD(t[o].add+k)));
}inline int Sum(int l,int r){return Sum(1,1,n,l,r);}
inline void Modify(int x){while(top[x]!=1){Add(dfn[top[x]],dfn[x]);x=f[top[x]];}Add(dfn[1],dfn[x]);
}
inline int Query(int x){int ans=0;while(top[x]!=1){SADD(ans,Sum(dfn[top[x]],dfn[x]));x=f[top[x]];}return SMOD(ans+Sum(dfn[1],dfn[x]));
}int main(){read(n),read(m);REP(i,2,n)read(x),Addedge(x+1,i);REP(i,1,m)read(x),read(y),read(z),++x,++y,++z,q[(i<<1)-1]=Questions{1,y,z,ans+i},q[i<<1]=Questions{-1,x-1,z,ans+i};std::sort(q+1,q+(m<<1)+1);DFS1(1);DFS2(1,1);int p=1;while(p<=(m<<1)&&!q[p].r)++p;//錯誤筆記： 要跳過之前以0開頭沒有用的空詢問 REP(i,1,n){Modify(i);while(p<=(m<<1)&&q[p].r==i)~q[p].opt?SADD(*q[p].ans,Query(q[p].z)):SDEL(*q[p].ans,Query(q[p].z)),++p;}REP(i,1,m)printf("%d\n",ans[i]);return flush(),0;
}
