【BZOJ3999】[TJOI2015]旅游（Link-Cut Tree）

时间：2023-12-19 12:20:56

【BZOJ3999】[TJOI2015]旅游（Link-Cut Tree）

题面

BZOJ

洛谷

题解

一道不难的\(LCT\)题（用树链剖分不是为难自己吗，这种有方向的东西用\(LCT\)不是方便那很多吗。。。）

维护一下"左子树的最小值减去右子树的最大值"的最大值就行了。

因为要支持翻转操作，所以右边反过来也支持一下，然后直接回答就行了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 50050

#define ls (t[x].ch[0])

#define rs (t[x].ch[1])

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Node

{

	int ch[2],ff,rev,v,tag;

	int lans,rans,mx,mn;

}t[MAX];

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].mx=max(t[x].v,max(t[ls].mx,t[rs].mx));

	t[x].mn=min(t[x].v,min(t[ls].mn,t[rs].mn));

	t[x].lans=max(max(t[ls].lans,t[rs].lans),max(t[rs].mx,t[x].v)-min(t[x].v,t[ls].mn));

	t[x].rans=max(max(t[ls].rans,t[rs].rans),max(t[ls].mx,t[x].v)-min(t[x].v,t[rs].mn));

}

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 putrev(int x)

{

	if(!x)return;

	t[x].rev^=1;swap(ls,rs);

	swap(t[x].lans,t[x].rans);

}

void puttag(int x,int w)

{

	if(!x)return;

	t[x].v+=w;t[x].tag+=w;

	t[x].mx+=w;t[x].mn+=w;

}

void pushdown(int x)

{

	if(t[x].tag)puttag(ls,t[x].tag),puttag(rs,t[x].tag),t[x].tag=0;

	if(t[x].rev)putrev(ls),putrev(rs),t[x].rev=0;

}

int S[MAX],top;

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[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);

		rotate(x);

	}

}

void access(int x){for(int y=0;x;y=x,x=t[x].ff)Splay(x),rs=y,pushup(x);}

void makeroot(int x){access(x);Splay(x);putrev(x);}

void split(int x,int y){makeroot(x);access(y);Splay(y);}

void link(int x,int y){makeroot(x);t[x].ff=y;}

int n,Q;

int main()

{

	n=read();t[0].mn=1e9;t[0].mx=-1e9;

	for(int i=1;i<=n;++i)t[i].v=t[i].mn=t[i].mx=read();

	for(int i=1;i<n;++i)link(read(),read());

	Q=read();

	while(Q--)

	{

		int u=read(),v=read(),w=read();

		split(u,v);printf("%d\n",t[v].lans);

		puttag(v,w);

	}

	return 0;

}

相关文章