【BZOJ3626】LCA（树链剖分，Link-Cut Tree）

【BZOJ3626】LCA（树链剖分，Link-Cut Tree）

题面

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。

设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。

有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。

（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Input

第一行2个整数n q。

接下来n-1行，分别表示点1到点n-1的父节点编号。

接下来q行，每行3个整数l r z。

Output

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

Sample Input

5 2

0

0

1

1

1 4 3

1 4 2

Sample Output

8

5

HINT

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

题解

我不会做的一道神题

OrzZsyDalao，看一眼就会做

如果暴力求，，，还是挺好的呀

咳咳，看正解

画画图

对于区间L~R，把每个点到根节点的路径全部+1

此时累加Z到根节点的路径权值和，发现就是答案

为啥呢

首先，我们可以知道LCA一定在Z到根节点的路径上

其次，深度就是LCA到根节点的路径长度

如果像上面那样计算，因为整个路径上都加了1

相当于加了整个LCA的深度

因此这样做就是对的

所以，直接离线处理就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define lson (t[x].ch[0])
#define rson (t[x].ch[1])
#define MAX 100000
#define MOD 201314
inline int read()
{
	int x=0,t=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=-1,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return x*t;
}
struct Node
{
	int ch[2],ff;
	int rev,pls;
	int size,sum,v;
}t[MAX];
int S[MAX],top,n,Q;
bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;}
void pushup(int x)
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
	t[x].sum=(t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].v)%MOD;
}
void Reverse(int x){swap(lson,rson);t[x].rev^=1;}
void pushdown(int x)
{
	if(t[x].rev)
	{
		if(lson)Reverse(lson);
		if(rson)Reverse(rson);
		t[x].rev^=1;
	}
	if(t[x].pls)
	{
		if(lson)
		{
			(t[lson].v+=t[x].pls)%=MOD;
			(t[lson].sum+=t[x].pls*t[lson].size%MOD)%=MOD;
			t[lson].pls=(t[lson].pls+t[x].pls)%MOD;
		}
		if(rson)
		{
			(t[rson].v+=t[x].pls)%=MOD;
			(t[rson].sum+=t[x].pls*t[rson].size%MOD)%=MOD;
			t[rson].pls=(t[rson].pls+t[x].pls)%MOD;
		}
		t[x].pls=0;
	}
}
void rotate(int x)
{
    int y=t[x].ff,z=t[y].ff;
    int k=t[y].ch[1]==x;
    if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;t[y].ff=x;
    pushup(y);pushup(x);
}
void Splay(int x)
{
    S[top=1]=x;
    for(int i=x;!isroot(i);i=t[i].ff)S[++top]=t[i].ff;
    while(top)pushdown(S[top--]);
    while(!isroot(x))
    {
        int y=t[x].ff,z=t[y].ff;
        if(!isroot(y))
            (t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
        rotate(x);
    }
}
void access(int x){for(int y=0;x;y=x,x=t[x].ff)Splay(x),t[x].ch[1]=y,pushup(x);}
void makeroot(int x){access(x);Splay(x);Reverse(x);}
void split(int x,int y){makeroot(x);access(y);Splay(y);}
void cut(int x,int y){split(x,y);t[y].ch[0]=t[x].ff=0;pushup(y);}
void link(int x,int y){makeroot(x);t[x].ff=y;}
struct Ask
{
	int id,z,i,opt;
}q[MAX*2];
bool cmp(Ask a,Ask b){return a.i<b.i;}
int ans[MAX],tot;
int main()
{
	n=read();Q=read();
	for(int i=2;i<=n;++i)
	{
		int u=read()+1;
		link(i,u);
	}
	for(int i=1;i<=Q;++i)
	{
		int l=read(),r=read()+1,z=read()+1;
		++tot;q[tot].id=q[tot+1].id=i;
		q[tot].z=q[tot+1].z=z;
		q[tot].i=l;q[tot+1].i=r;
		q[tot].opt=-1;q[++tot].opt=1;
	}
	sort(&q[1],&q[tot+1],cmp);
	int pos=1;
	while(!q[pos].i&&pos<tot)++pos;
	for(int i=1;i<=n;++i)
	{
		split(i,1);
		t[1].v=(t[1].v+1)%MOD;
		t[1].sum=(t[1].sum+t[1].size)%MOD;
		t[1].pls=(t[1].pls+1)%MOD;
		while(q[pos].i==i&&pos<=tot)
		{
			split(q[pos].z,1);
			ans[q[pos].id]=(ans[q[pos].id]+q[pos].opt*t[1].sum%MOD+MOD)%MOD;
			++pos;
		}
	}
	for(int i=1;i<=Q;++i)printf("%d\n",ans[i]%MOD);
	return 0;
}