传送门
树链剖分好题。
对于每个点维护一个值vi" role="presentation" style="position: relative;">vivi,当考虑点i时我们将它到根的路径上的所有数的v值+1。
这样维护下来v和dep的值是相等的。
当这个更新到达点i时,从1到z这条路径的v值之和就是∑j=1idep[lca(j,z)]" role="presentation" style="position: relative;">∑ij=1dep[lca(j,z)]∑j=1idep[lca(j,z)]
这样的话一个询问(l,r,z)可以转化成calc(1,r,z)-calc(1.l-1,z)。
这样就可以离线用树剖维护了。
代码:
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 50005
#define mod 201314
using namespace std;
int n,m,first[N],dep[N],top[N],hson[N],fa[N],siz[N],num[N],cnt=0,tot=0,sig=0,ans[N];
struct edge{int v,next;}e[N<<1];
struct Q{int id,pos,tmp,z;}q[N<<1];
struct Node{int l,r,sum,lz;}T[N<<2];
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs1(int p){
siz[p]=1;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
inline void dfs2(int p,int tp){
top[p]=tp,num[p]=++sig;
if(!hson[p])return;
dfs2(hson[p],tp);
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v!=hson[p])dfs2(v,v);
}
}
inline void pushup(int p){T[p].sum=(T[lc].sum+T[rc].sum)%mod;}
inline void pushnow(int p,int v){(T[p].sum+=v*(T[p].r-T[p].l+1))%=mod,(T[p].lz+=v)%=mod;}
inline void pushdown(int p){if(T[p].lz)pushnow(lc,T[p].lz),pushnow(rc,T[p].lz),T[p].lz=0;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return;
build(lc,l,mid),build(rc,mid+1,r);
}
inline void update(int p,int ql,int qr,int v){
if(ql>T[p].r||qr<T[p].l)return;
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline int query(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return (query(lc,ql,mid)+query(rc,mid+1,qr))%mod;
}
inline void change(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])x^=y,y^=x,x^=y;
update(1,num[top[x]],num[x],v),x=fa[top[x]];
}
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
update(1,num[y],num[x],v);
}
inline int ask(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])x^=y,y^=x,x^=y;
ans+=query(1,num[top[x]],num[x]),x=fa[top[x]];
}
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
return ans+query(1,num[y],num[x]);
}
inline bool cmp(Q a,Q b){return a.pos<b.pos;}
int main(){
n=read(),m=read();
for(int i=2;i<=n;++i)fa[i]=read()+1,add(fa[i],i);
dfs1(1),dfs2(1,1),build(1,1,n);
for(int i=1;i<=m;++i){
int l=read()+1,r=read()+1;
q[++tot].z=read()+1,q[tot].id=i,q[tot].pos=l-1,q[tot].tmp=-1;
q[++tot].z=q[tot-1].z,q[tot].id=i,q[tot].pos=r,q[tot].tmp=1;
}
sort(q+1,q+tot+1,cmp);
int j=0;
while(!q[j+1].pos)++j;
for(int i=1;i<=n;++i){
change(1,i,1);
while(q[j+1].pos==i)++j,(ans[q[j].id]+=q[j].tmp*ask(1,q[j].z))%=mod;
}
for(int i=1;i<=m;++i)printf("%d\n",(ans[i]+mod)%mod);
return 0;
}