[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)]$

输入输出格式

输入格式：

第一行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。

题解

~~既然题目是LCA那么肯定跟LCA没关系啦~~

根据yy可得，求$dep[LCA(a,b)]$相当于把$a$到根的每个点$+1$，然后统计$b$到根的点值和

然后~~正常的想法是~~枚举$l$到$r$，然后每个点都区间修改，在查询区间和

但是这样是不行的，因为在算后面的时候前面的算了多次

考虑差分，从小到大枚举每个点，同时区间修改，枚举到$l$记录一下，枚举到$r$记录一下，答案就是$ansr-ansl$

这样就得离线一下询问了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=5e4+1,mod=201314;
struct p{
	int x,lazy;
}s[MAX<<2];
struct q{
	int x,y;
}c[MAX<<1];
struct o{
	int L,id,x;
	bool fl;
	bool operator< (const o& a)
	const{
		return L<a.L;
	}
}qu[MAX<<1];
int n,m,num,tot,cnt;
int h[MAX],fa[MAX],d[MAX],top[MAX],id[MAX],siz[MAX],son[MAX];
int ans[2][MAX];
int read()
{
	int x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y)
{
	c[++num]=(q){h[x],y},h[x]=num;
	c[++num]=(q){h[y],x},h[y]=num;
}
void dfs(int x,int f)
{
	d[x]=d[f]+1,fa[x]=f,siz[x]=1;
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if(y==f) continue;
	  	dfs(y,x),siz[x]+=siz[y];
	  	if(siz[y]>siz[son[x]]) son[x]=y;
	  }
}
void dfs1(int x,int tp)
{
	top[x]=tp,id[x]=++cnt;
	if(son[x]) dfs1(son[x],tp);
	else return;
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if(y==son[x]||y==fa[x]) continue;
	  	dfs1(y,y);
	  }
}
void down(int l,int r,int k)
{
	int f=s[k].lazy;
	if(!f) return;
	s[k].lazy=0;
	s[tl].x=(s[tl].x+f*(mid-l+1))%mod,s[tl].lazy+=f;
	s[tr].x=(s[tr].x+f*(r-mid))%mod,s[tr].lazy+=f;
}
void pus(int k)
{
	s[k].x=(s[tl].x+s[tr].x)%mod;
}
void change(int l,int r,int k,int L,int R)
{
	if(l==L&&r==R)
	{
		s[k].x=(s[k].x+r-l+1)%mod,++s[k].lazy;
		return;
	}
	down(l,r,k);
	if(R<=mid) change(l,mid,tl,L,R);
	else if(L>mid) change(mid+1,r,tr,L,R);
	else change(l,mid,tl,L,mid),change(mid+1,r,tr,mid+1,R);
	pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
	if(l==L&&r==R) return s[k].x;
	down(l,r,k);
	if(R<=mid) return ask(l,mid,tl,L,R);
	else if(L>mid) return ask(mid+1,r,tr,L,R);
	return (ask(l,mid,tl,L,mid)+ask(mid+1,r,tr,mid+1,R))%mod;
}
void CHANGE(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		change(1,n,1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	change(1,n,1,id[x],id[y]);
}
int ASK(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		ans=(ans+ask(1,n,1,id[top[x]],id[x]))%mod;
		x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	return (ans+ask(1,n,1,id[x],id[y]))%mod;
}
int main()
{
	n=read(),m=read();
	for(int i=2;i<=n;++i)
	  add(i,read()+1);
	dfs(1,0),dfs1(1,1);
	for(int i=1;i<=m;++i)
	  qu[++tot].L=read(),qu[++tot].L=read()+1,qu[tot-1].id=qu[tot].id=i,qu[tot-1].x=qu[tot].x=read()+1,qu[tot].fl=1;
	sort(qu+1,qu+1+tot);
	int l=0;
	for(int i=1;i<=tot;++i)
	  {
	  	while(l<qu[i].L) CHANGE(1,++l);
	  	ans[qu[i].fl][qu[i].id]=ASK(1,qu[i].x);
	  }
	for(int i=1;i<=m;++i)
	  printf("%d\n",(ans[1][i]-ans[0][i]+mod)%mod);
	return 0;
}

题目