本来是打算作为树剖练习的最后一题的，结果一直WA。

本来以为是自己写的太丑。

最后发现5w的数据

我开了10w的数组

然而有一个数组要×2

哦，好棒棒。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define foru(i,x,y) for(LL i=x;i<=y;i++)  6 using namespace std;  7 typedef int LL;  8 const LL N=2e5;  9 const LL mod=201314; 10 struct edge{LL to,nxt;}e[2*N]; 11 struct node{LL s,t;}t[10*N]; 12 struct que{LL id,flag,p;}a[N]; 13 LL f[N],b[N],d[N],id[N],ans[N],siz[N],son[N],top[N],head[N], 14    cnt,ne,n,m,nq,q[N]; 15      16 bool cmp(que a,que b){
   return a.p
         
          siz[son[k]])son[k]=v; 30     } 31 } 32      33 void build(LL k,LL tp){ 34     id[k]=++cnt;top[k]=tp; 35     if(son[k])build(son[k],tp); 36     for(LL i=head[k];i;i=e[i].nxt){ 37         LL v=e[i].to; 38         if(v!=son[k]&&v!=f[k])build(v,v); 39     } 40 } 41      42 #define mid ((L+R)>>1) 43 #define ls (k<<1) 44 #define rs ls+1 45      46 void pd(LL k,LL L,LL R){ 47     t[k].s+=t[k].t*(R-L+1); 48     if(t[k].s>=mod)t[k].s%=mod; 49     t[ls].t+=t[k].t; t[rs].t+=t[k].t; 50     t[k].t=0; 51 } 52      53 void pu(LL k,LL L,LL R){ 54     t[k].s=t[ls].s+t[rs].s; 55     if(t[k].s>=mod)t[k].s%=mod; 56 } 57      58 void update(LL k,LL L,LL R,LL l,LL r,LL x){ 59     pd(k,L,R); 60     if(r
          
           R)return; 61 if(l<=L&&R<=r){t[k].t+=x;return;} 62 update(ls,L,mid,l,r,x); update(rs,mid+1,R,l,r,x); 63 pd(ls,L,mid);pd(rs,mid+1,R); 64 pu(k,L,R); 65 } 66 67 LL qur(LL k,LL L,LL R,LL l,LL r){ 68 pd(k,L,R); 69 if(l>R||r
           
            =mod)ret%=mod; 79 x=f[top[x]]; 80 } 81 return ret; 82 } 83 84 void change(LL x){ 85 while(x){ 86 update(1,1,cnt,id[top[x]],id[x],1); 87 x=f[top[x]]; 88 } 89 } 90 int main(){ 91 LL x,l,r; 92 scanf("%d%d",&n,&m); 93 foru(i,2,n){ 94 scanf("%d",&x);x++; 95 add(x,i);add(i,x); 96 } 97 foru(i,1,m){ 98 scanf("%d%d%d",&l,&r,&q[i]);q[i]++; 99 a[++nq].p=l;a[nq].id=i;a[nq].flag=-1;100 a[++nq].p=r+1;a[nq].id=i;a[nq].flag=1;101 }102 dfs(1,0,1);103 build(1,1);104 sort(a+1,a+1+nq,cmp);105 LL j=0;106 while(!a[j+1].p)j++;107 foru(i,1,n){108 change(i);109 while(a[j+1].p==i)j++,ans[a[j].id]+=get(q[a[j].id])*a[j].flag;110 }111 foru(i,1,m)printf("%d\n",(ans[i]+mod)%mod);112 return 0;113 }