给出一个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取模输出

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

数据已加强 by saffah

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<cmath>  6 #include<vector>  7 #define lc rt<<1  8 #define rc rt<<1|1  9 using namespace std; 10 const int mod=201314; 11 const int mxn=50010; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();} 16     return x*f; 17 } 18 struct edge{int v,nxt;}e[mxn<<1]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v){ 21     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 22 } 23 struct node{int fa,son;int top,size;int w,e;}t[mxn]; 24 int dep[mxn],sz=0; 25 void DFS1(int u,int fa){ 26     dep[u]=dep[fa]+1; 27     t[u].fa=fa;t[u].size=1; 28     for(int i=hd[u];i;i=e[i].nxt){ 29         int v=e[i].v; 30         DFS1(v,u); 31         t[u].size+=t[v].size; 32         if(t[v].size>t[t[u].son].size){ 33             t[u].son=v; 34         } 35     } 36     return; 37 } 38 void DFS2(int u,int top){ 39     t[u].w=++sz;t[u].top=top; 40     if(t[u].son){ 41         DFS2(t[u].son,top); 42         for(int i=hd[u];i;i=e[i].nxt){ 43             int v=e[i].v; 44             if(v!=t[u].son && v!=t[u].fa){ 45                 DFS2(v,v); 46             } 47         } 48     } 49     t[u].e=sz; 50     return; 51 } 52 struct sgt{int sum,mk;}st[mxn<<2]; 53 void pushup(int rt){st[rt].sum=(st[lc].sum+st[rc].sum)%mod;return;} 54 void pushdown(int l,int r,int rt){ 55     if(st[rt].mk){ 56         st[lc].mk+=st[rt].mk; 57         st[rc].mk+=st[rt].mk; 58         int mid=(l+r)>>1; 59         (st[lc].sum+=st[rt].mk*(mid-l+1))%=mod; 60         (st[rc].sum+=st[rt].mk*(r-mid))%=mod; 61         st[rt].mk=0; 62     } 63     return; 64 } 65 void update(int L,int R,int v,int l,int r,int rt){ 66     if(L<=l && r<=R){ 67         st[rt].mk+=v; 68         (st[rt].sum+=v*(r-l+1))%=mod; 69         return; 70     } 71     if(st[rt].mk)pushdown(l,r,rt); 72     int mid=(l+r)>>1; 73     if(L<=mid)update(L,R,v,l,mid,lc); 74     if(R>mid)update(L,R,v,mid+1,r,rc); 75     pushup(rt); 76     return; 77 } 78 int qsum(int L,int R,int l,int r,int rt){ 79     if(L<=l && r<=R){return st[rt].sum;} 80     if(st[rt].mk)pushdown(l,r,rt); 81     int mid=(l+r)>>1; 82     int res=0; 83     if(L<=mid) res+=qsum(L,R,l,mid,lc); 84     if(R>mid) res+=qsum(L,R,mid+1,r,rc); 85     return res%mod; 86 } 87 void tadd(int x,int y,int v){ 88     while(t[x].top!=t[y].top){ 89         if(dep[t[x].top]<dep[t[y].top])swap(x,y); 90         update(t[t[x].top].w,t[x].w,v,1,sz,1); 91         x=t[t[x].top].fa; 92     } 93     if(dep[x]>dep[y])swap(x,y); 94     update(t[x].w,t[y].w,v,1,sz,1); 95     return; 96 } 97 int asksum(int x,int y){ 98     int res=0; 99     while(t[x].top!=t[y].top){100         if(dep[t[x].top]<dep[t[y].top])swap(x,y);101         (res+=qsum(t[t[x].top].w,t[x].w,1,sz,1))%=mod;102         x=t[t[x].top].fa;103     }104     if(dep[x]>dep[y])swap(x,y);105     res+=qsum(t[x].w,t[y].w,1,sz,1);106     return res;107 }108 struct query{109     int x,v,z;int id;110 }q[mxn<<1];111 int qct=0;112 int cmp(const query a,const query b){113     if(a.x!=b.x)return a.x<b.x;114     return a.id<b.id;115 }116 int ans[mxn];117 int n,Q;118 int main()119 {120     n=read();Q=read();121     int i,j;122     for(i=2;i<=n;i++){//点编号整体+1 123         j=read()+1;124         add_edge(j,i);125     }126     DFS1(1,0);127     DFS2(1,1);128     int x,y,z;129     for(i=1;i<=Q;i++){130         x=read()+1;y=read()+1;z=read()+1;131         q[++qct].id=i;q[qct].z=z;q[qct].x=x-1;q[qct].v=1;132         q[++qct].id=i;q[qct].z=z;q[qct].x=y;q[qct].v=-1;133     }134     sort(q+1,q+qct+1,cmp);135     int hed=1;136     for(i=1;i<=qct;i++){137         while(hed<=q[i].x){138             tadd(hed,1,1);139             hed++;140         }141         if(q[i].v==1)ans[q[i].id]-=asksum(q[i].z,1);142         else ans[q[i].id]+=asksum(q[i].z,1);//差分答案 143     }144     for(i=1;i<=Q;i++)printf("%d\n",(ans[i]%mod+mod)%mod);145     return 0;146 }