【SPOJ】QTREE7（Link-Cut Tree）

题面

洛谷

Vjudge

题解

和QTREE6的本质是一样的：维护同色联通块

那么，QTREE6同理，对于两种颜色分别维护一棵\(LCT\)

每次只修改和它父亲的连边。

考虑如何维护最大值

因为每次\(access\)会删去一个数，所以我们肯定不能够只维护最大值。

因此，对于每一个节点，额外维护一个\(multiset\)（当然，可删堆，\(map\)之类的也行）

每次用\(multiset\)维护虚子树的最值，拿过去更新即可。

最后的答案和QTREE6是一样的，

找到这个联通块的最浅父亲，维护一下子树最值就行啦。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111111

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

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

inline int read()

{

    RG int x=0,t=1;RG 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;

}

int W[MAX];

struct Link_Cut_Tree

{

	struct Node

	{

		int ch[2],ff;

		int mx;

		multiset<int> S;

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

		if(!t[x].S.empty())t[x].mx=max(t[x].mx,*t[x].S.rbegin());

	}

	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)

	{

		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);

		}

		pushup(x);

	}

	void access(int x)

	{

		for(int y=0;x;y=x,x=t[x].ff)

		{

			Splay(x);

			if(rs)t[x].S.insert(t[rs].mx);

			rs=y;

			if(rs)t[x].S.erase(t[rs].mx);

			pushup(x);

		}

	}

	int findroot(int x){access(x);Splay(x);while(ls)x=ls;Splay(x);return x;}

	void link(int x,int y){if(!y)return;access(y);Splay(y);Splay(x);t[x].ff=y;t[y].ch[1]=x;pushup(y);}

	void cut(int x,int y){if(!y)return;access(x);Splay(x);ls=t[ls].ff=0;pushup(x);}

}LCT[2];

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1,fa[MAX],n,Q,c[MAX];

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

void dfs(int u,int ff)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		fa[v]=u;LCT[c[v]].link(v,u);dfs(v,u);

	}

}

int main()

{

	n=read();

	for(int i=1,u,v;i<n;++i)u=read(),v=read(),Add(u,v),Add(v,u);

	for(int i=1;i<=n;++i)c[i]=read();

	for(int i=1;i<=n;++i)W[i]=read();

	LCT[0].t[0].mx=LCT[1].t[0].mx=-2e9;

	dfs(1,0);Q=read();

	while(Q--)

	{

		int opt=read(),u=read();

		if(opt==0)

		{

			int ff=LCT[c[u]].findroot(u);

			if(c[u]==c[ff])printf("%d\n",LCT[c[u]].t[ff].mx);

			else printf("%d\n",LCT[c[u]].t[LCT[c[u]].t[ff].ch[1]].mx);

		}

		else if(opt==1)LCT[c[u]].cut(u,fa[u]),c[u]^=1,LCT[c[u]].link(u,fa[u]);

		else

		{

			LCT[c[u]].access(u);LCT[c[u]].Splay(u);

			W[u]=read();LCT[c[u]].pushup(u);

		}

	}

	return 0;

}