[LNOI2014]LCA T18 D71

[ LNOI2014]LCA

树剖+前缀和思维

思路：

​ lca(i,z)的深度就是i相当于i到根节点的路径上权值加1，z到根节点的路径上的权值和

​ 对于 l<=i<=r ,将所有的i到根节点路径权值加1，考虑前缀和，那么答案就是ans[r]-ans[l-1];

参考代码

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define si size()
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid (t[p].l+t[p].r)/2 
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=1e5+7;
const int mod=201314;

int n,q,ans[qs];
vector<int> v[qs];
int dep[qs],son[qs],f[qs],sz[qs],top[qs],fr[qs],cnt;
pii id[qs];

struct node{
	int x,z,id,sta;
	node(){}
	node(int x,int z,int id,int sta):x(x),z(z),id(id),sta(sta){};
}A[qs];

struct Tree{
	int l,r,val,add;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define val(x) t[x].val
	#define add(x) t[x].add
}t[qs<<2];

void build(int p,int l,int r){
	l(p)=l,r(p)=r;add(p)=0;val(p)=0;
	if(l==r) return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}

void down(int p){
	if(!add(p)) return;
	val(ls)=(val(ls)+add(p)*(r(ls)-l(ls)+1))%mod;
	val(rs)=(val(rs)+add(p)*(r(rs)-l(rs)+1))%mod;
	add(ls)=(add(ls)+add(p))%mod;
	add(rs)=(add(rs)+add(p))%mod;
	add(p)=0;
}

void pushup(int p){ val(p)=(val(ls)+val(rs))%mod;}

void update(int p,int l,int r,ll val){
	if(l<=l(p)&&r>=r(p)) {
		add(p)=(add(p)+val)%mod;
		val(p)=(val(p)+(r(p)-l(p)+1)*val)%mod;
		return;
	}
	down(p);
	if(l<=mid) update(ls,l,r,val);
	if(r>mid) update(rs,l,r,val);
	pushup(p);
}

ll ask(int p,int l,int r){
	if(l<=l(p)&&r>=r(p)) return val(p);
	down(p);
	ll val=0;
	if(l<=mid) val=(val+ask(ls,l,r))%mod;
	if(r>mid) val=(val+ask(rs,l,r))%mod;
	return val;
}


void dfs(int x,int fa){
	f[x]=fa; son[x]=0; sz[x]=1; dep[x]=dep[fa]+1;
	int ms=0;
	for(int i=0;i<v[x].si;++i){
		int p=v[x][i];
		if(p==fa) continue;
		dfs(p,x);
		sz[x]+=sz[p];
		if(sz[p]>ms) ms=sz[p],son[x]=p;
	}
}

void dfn(int x,int op){
	id[x].fi=++cnt;
	top[x]=op;
	fr[cnt]=x;
	if(!son[x]){
		id[x].se=cnt; return;
	}
	dfn(son[x],op);
	for(int i=0;i<v[x].si;++i){
		int p=v[x][i];
		if(p==f[x]||p==son[x]) continue;
		dfn(p,p);
	}
	id[x].se=cnt;
}

void updRange(int x,int y,int k){
	k%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,id[top[x]].fi,id[x].fi,k);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(1,id[x].fi,id[y].fi,k);
} 

ll qRange(int x,int y){
	ll ans=0,res;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=ask(1,id[top[x]].fi,id[x].fi);
		ans=(ans+res)%mod;
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=ask(1,id[x].fi,id[y].fi);
	ans=(ans+res)%mod;
	return ans;
}

bool cmp(node a,node b){
	return a.x<b.x;
}



int main(){
	n=read(),q=read();
	cnt=0;
	int x;
	
	for(int i=1;i<n;++i){
		x=read();
		v[x].pb(i);	
		
	}

	dfs(0,0);
	
	dfn(0,0);
	
	build(1,1,n);
	int l,r,z;
	int ct=0;
	
	for(int i=1;i<=q;++i){
		l=read(),r=read(),z=read();
		A[++ct]=node(l-1,z,i,-1);
		A[++ct]=node(r,z,i,1);
	}
	sort(A+1,A+1+ct,cmp);
	for(int i=1;i<=ct;++i){
		int fx=A[i].x,fid=A[i].id,fz=A[i].z,fs=A[i].sta;
		for(int j=A[i-1].x+1;j<=fx;++j) updRange(0,j,1);
		ll res=qRange(0,fz)*fs;
		ans[fid]=(ans[fid]+res+mod)%mod;
	}
	for(int i=1;i<=q;++i){
		cout<<ans[i]<<"\n";
	}
	return 0;
}