给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <complex>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cstdio>
  8 #include <vector>
  9 #include <cmath>
 10 #include <queue>
 11 #include <stack>
 12 #include <map>
 13 #include <set>
 14 #define inf (1<<30)
 15 #define rhl (201314)
 16 #define N (50005)
 17 #define il inline
 18 #define RG register
 19 #define ll long long
 20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 21 
 22 using namespace std;
 23 
 24 struct edge{ int nt,to; }g[N];
 25 
 26 ll sum[130*N];
 27 int lazy[130*N],ls[130*N],rs[130*N],rt[N],ssz;
 28 int head[N],top[N],fa[N],son[N],tid[N],dep[N],sz[N],n,q,cnt,num;
 29 
 30 il int gi(){
 31     RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
 32     if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x;
 33 }
 34 
 35 il void insert(RG int from,RG int to){ g[++num]=(edge){head[from],to},head[from]=num; return; }
 36 
 37 il void dfs1(RG int x,RG int p){
 38     fa[x]=p,dep[x]=dep[p]+1,sz[x]=1; RG int v;
 39     for (RG int i=head[x];i;i=g[i].nt){
 40     v=g[i].to; if (v==p) continue;
 41     dfs1(v,x); sz[x]+=sz[v];
 42     if (sz[son[x]]<=sz[v]) son[x]=v;
 43     }
 44     return;
 45 }
 46 
 47 il void dfs2(RG int x,RG int p,RG int anc){
 48     top[x]=anc,tid[x]=++cnt;
 49     if (son[x]) dfs2(son[x],x,anc); RG int v;
 50     for (RG int i=head[x];i;i=g[i].nt){
 51     v=g[i].to; if (v==p || v==son[x]) continue;
 52     dfs2(v,x,v);
 53     }
 54     return;
 55 }
 56 
 57 il void update(RG int x,RG int &y,RG int l,RG int r,RG int xl,RG int xr){
 58     y=++ssz; sum[y]=sum[x],lazy[y]=lazy[x],ls[y]=ls[x],rs[y]=rs[x];
 59     if (xl<=l && r<=xr){ (sum[y]+=r-l+1)%=rhl,lazy[y]++; return; }
 60     RG int mid=(l+r)>>1;
 61     if (xr<=mid) update(ls[x],ls[y],l,mid,xl,xr);
 62     else if (xl>mid) update(rs[x],rs[y],mid+1,r,xl,xr);
 63     else update(ls[x],ls[y],l,mid,xl,mid),update(rs[x],rs[y],mid+1,r,mid+1,xr);
 64     sum[y]=(sum[ls[y]]+sum[rs[y]]+(ll)lazy[y]*(ll)(r-l+1))%rhl; return;
 65 }
 66 
 67 il int query(RG int x,RG int y,RG int l,RG int r,RG int xl,RG int xr,RG ll la){
 68     if (xl<=l && r<=xr) return (int)(sum[y]-sum[x]+la*(ll)(r-l+1)+rhl)%rhl;
 69     RG int mid=(l+r)>>1; la+=lazy[y]-lazy[x];
 70     if (xr<=mid) return query(ls[x],ls[y],l,mid,xl,xr,la);
 71     else if (xl>mid) return query(rs[x],rs[y],mid+1,r,xl,xr,la);
 72     else return query(ls[x],ls[y],l,mid,xl,mid,la)+query(rs[x],rs[y],mid+1,r,mid+1,xr,la);
 73 }
 74 
 75 il void change(RG int x){
 76     RG int la=rt[x-1],u=x;
 77     while (u){
 78     update(la,rt[x],1,n,tid[top[u]],tid[u]);
 79     la=rt[x],u=fa[top[u]];
 80     }
 81     return;
 82 }
 83 
 84 il int Query(RG int x,RG int l,RG int r){
 85     RG int res=0;
 86     while (x){
 87     (res+=query(rt[l-1],rt[r],1,n,tid[top[x]],tid[x],0))%=rhl;
 88     x=fa[top[x]];
 89     }
 90     return res;
 91 }
 92 
 93 il void work(){
 94     n=gi(),q=gi(); RG int l,r,z;
 95     for (RG int i=2;i<=n;++i) fa[i]=gi()+1,insert(fa[i],i);
 96     dfs1(1,0),dfs2(1,0,1); for (RG int i=1;i<=n;++i) change(i);
 97     for (RG int i=1;i<=q;++i){
 98     l=gi()+1,r=gi()+1,z=gi()+1;
 99     printf("%d\n",Query(z,l,r));
100     }
101     return;
102 }
103 
104 int main(){
105     File("lca");
106     work();
107     return 0;
108 }