[LNOI2014] LCA

题目描述

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求 $sum_{l leq i leq r}dep[LCA(i,z)]∑l≤i≤rdep[LCA(i,z)]$

输入输出格式

输入格式：

第一行2个整数n q。接下来n-1行，分别表示点1到点n-1的父节点编号。接下来q行，每行3个整数l r z。

输出格式：

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

输入输出样例

输入样例#1：

输出样例#1：

8
5

说明

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

可以发现求a与b的lca的深度+1，可以先把b到根的路径上都+1，然后查询一下a到根的权值和就行了。。

有了这个思路之后，我们就可以离线处理出前k个点到根的路径+1,然后前缀和做一下差就可以回答询问了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long
#define pb push_back
#define maxn 50005
using namespace std;
const int ha=201314;
struct node{
	int O,num,p;
};
vector<node> ask[maxn];
vector<int> g[maxn];
int son[maxn],siz[maxn],dep[maxn];
int cl[maxn],f[maxn],dfn[maxn];
int dc=0,dy[maxn],n,Q,ff,ans[maxn];
int le,ri,v,sum[maxn<<2|1],tag[maxn<<2|1];

inline int add(int x,int y){
	x+=y;
	return x>=ha?x-ha:x;
}

void dfs1(int x,int fa){
	f[x]=fa,dep[x]=dep[fa]+1;
	siz[x]=1;
	
	int to;
	for(int i=g[x].size()-1;i>=0;i--){
		to=g[x][i];
		if(to==fa) continue;
		dfs1(to,x);
		
		siz[x]+=siz[to];
		if(!son[x]||siz[to]>siz[son[x]]) son[x]=to;
	}
}

void dfs2(int x,int tp){
	dfn[x]=++dc,dy[dc]=x;
	cl[x]=tp;
	
	if(!son[x]) return;
	
	dfs2(son[x],tp);
	
	int to;
	for(int i=g[x].size()-1;i>=0;i--){
		to=g[x][i];
		if(to==f[x]||to==son[x]) continue;
		
		dfs2(to,to);
	}
}

void update(int o,int l,int r){
	if(l>=le&&r<=ri){
		sum[o]=add(sum[o],r-l+1);
		tag[o]=add(tag[o],1);
		return;
	}
	
	int lc=o<<1,rc=(o<<1)|1,mid=l+r>>1;
	if(le<=mid) update(lc,l,mid);
	if(ri>mid) update(rc,mid+1,r);
	
	sum[o]=tag[o]*(r-l+1)+sum[lc]+sum[rc];
	if(sum[o]>=ha) sum[o]%=ha;
}

int query(int o,int l,int r,int ad){
	if(l>=le&&r<=ri) return (sum[o]+ad*(r-l+1))%ha;
	int lc=o<<1,rc=(o<<1)|1,mid=l+r>>1,an=0;
	if(le<=mid) an=add(an,query(lc,l,mid,add(ad,tag[o])));
	if(ri>mid) 	an=add(an,query(rc,mid+1,r,add(ad,tag[o])));
	
	return an;
}

inline void init(int x){
	while(x){
		le=dfn[cl[x]],ri=dfn[x];
		update(1,1,n);
		x=f[cl[x]];
	}
}

inline int valtoroot(int x){
	int an=0;
	while(x){
		le=dfn[cl[x]],ri=dfn[x];
		an=add(an,query(1,1,n,0));
		x=f[cl[x]];
	}
	
	return an;
}

inline void solve(){
	node x;
	
	for(int i=1;i<=n;i++){
		init(i);
		for(int j=ask[i].size()-1;j>=0;j--){
			x=ask[i][j];
			if(x.O>0) ans[x.num]=add(ans[x.num],valtoroot(x.p));
			else ans[x.num]=add(ans[x.num],ha-valtoroot(x.p));
		}
	}
}

int main(){
	scanf("%d%d",&n,&Q);
	for(int i=2;i<=n;i++){
		scanf("%d",&ff);
		ff++,g[ff].pb(i);
	}
	
	for(int i=1;i<=Q;i++){
		scanf("%d%d%d",&le,&ri,&v);
		v++,le++,ri++;
		ask[le-1].pb((node){-1,i,v});
		ask[ri].pb((node){1,i,v});
	}
	
	dep[0]=0;
	dfs1(1,0);
	dfs2(1,1);
	
	solve();
	
	for(int i=1;i<=Q;i++) printf("%d
",ans[i]);
	return 0;
}