题目传送带

貌似是线段树的问题，毕竟是动态开点线段树，建树有点小问题。

code

#include<bits/stdc++.h>
using namespace std;
const int mod=201314;
int ans[500005],tot,res,n,cnt,m,u,l,r,z,top[50005],head[100005],id[50005],f[50005],son[50005],dep[50005],size[50005];
struct node{
	int to,nxt;
}e[100005];
struct node2{
	int l,r,sum,lazy;
}tr[200005];
struct query{
	int pos,w,id,flag;
}q[100005];
bool cmp(query a,query b){
	return a.pos<b.pos;
}
void add(int x,int y){
	e[++cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
void dfs(int x,int pre,int depth){
	size[x]=1;
	dep[x]=depth;
	f[x]=pre;
	int maxx=-1;
	for(register int i=head[x];i;i=e[i].nxt){
		if(e[i].to==pre){
			continue;
		}
		dfs(e[i].to,x,depth+1);
		size[x]+=size[e[i].to];
		if(maxx<size[e[i].to]){
			maxx=size[e[i].to];
			son[x]=e[i].to;
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	id[u]=++res;
	if(!son[u]){
		return ;
	}
	dfs2(son[u],tp);
	for(register int i=head[u];i;i=e[i].nxt){
		if(e[i].to==f[u]||e[i].to==son[u]){
			continue;
		}
		dfs2(e[i].to,e[i].to); 
	}
} 
void push_down(int p){
	if(tr[p].lazy){
		tr[p*2].lazy+=tr[p].lazy;
		tr[p*2+1].lazy+=tr[p].lazy;
		int mid=(tr[p].l+tr[p].r)/2;
		tr[p*2].sum+=tr[p].lazy*(mid-tr[p].l+1);
		tr[p*2].sum+=tr[p].lazy*(tr[p].r-mid);
		tr[p].lazy=0;
	}
}
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	if(l==r){
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void quxiu(int p,int l,int r,int k){
	if(tr[p].l>r&&tr[p].r<l){
		return ; 
	}
	if(tr[p].l>=l&&tr[p].r<=r){
		tr[p].sum+=k*(tr[p].r-tr[p].l+1);
		tr[p].lazy+=k; 
		return ;
	}
	//cout<<tr[p].l<<" "<<tr[p].r<<" "<<l<<" "<<r<<'\n';
	push_down(p);
	if(tr[p*2].r>=l){
		quxiu(p*2,l,r,k);
	}
	if(tr[p*2+1].l<=r){
		quxiu(p*2+1,l,r,k);
	}
	tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
}
int qucha(int p,int l,int r){
	if(tr[p].l>r&&tr[p].r<l){
		return 0; 
	}
	if(tr[p].l>=l&&tr[p].r<=r){
		return tr[p].sum; 
	}
	push_down(p);
	int s=0;
	if(tr[p*2].r<=l){
		s+=qucha(p*2,l,r);
	}
	if(tr[p*2+1].l>=r){
		s+=qucha(p*2+1,l,r);
	} 
	return s;
}
void qx(int x,int y,int k){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		quxiu(1,id[top[x]],id[x],k);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	quxiu(1,id[x],id[y],k);
} 
int qr(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		ans+=qucha(1,id[top[x]],id[x]);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	ans+=qucha(1,id[x],id[y]);
	return ans;
} 
int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	cin>>n>>m;
	for(register int i=2;i<=n;i++){
		cin>>u;
		u++; 
		add(u,i);
	}
	dfs(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	for(register int i=1;i<=m;i++){
		cin>>l>>r>>z;
		r++;
		z++;
		q[++tot].pos=l-1;
		q[tot].w=z;
		q[tot].id=i;
		q[tot].flag=0;
		q[++tot].pos=r;
		q[tot].w=z;
		q[tot].id=i;
		q[tot].flag=1;
	}
	sort(q+1,q+tot+1,cmp);
	for(register int i=0;i<tot;i++){
		for(register int j=1;j<=q[i].pos;j++){
			qx(1,j,1);
		}
		if(q[i].flag){
			ans[q[i].id]+=qr(1,q[i].w);
		}
		else{
			//ans[q[i].id]-=qr(1,q[i].w);
		}
		ans[q[i].id]=(ans[q[i].id]+mod)%mod;
	} 
	for(register int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}