题意

一棵树,每个点初始有个点权和颜色(输入会给你)

0 u :询问所有u,v路径上的最大点权,要满足u,v路径上所有点的颜色都相同

1 u :反转u的颜色

2 u w :把u的点权改成w

\(color_i\in [0,1],w_i\in [−10^9,10^9],n,m≤10^5\)

sol

和\(QTree 6\)很像啊。丢个链接就跑

只要额外对每个点维护一个虚子树的最大权值即可。

开一个\(multiset\)写起来比较爽。

然后就做完了

code

我不会说我因为快读打错了debug了一个晚上的

#include<cstdio>

#include<algorithm>

#include<vector>

#include<set>

using namespace std;

int gi()

{

	int x=0,w=1;char ch=getchar();

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

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 1e5+5;

int n,m,col[N],w[N],fa[N];

vector<int>G[N];

struct LCT{

	int fa[N],ch[2][N],mx[N];

	multiset<int>S[N];

	bool son(int x){return x==ch[1][fa[x]];}

	bool isroot(int x)

		{

			return x!=ch[0][fa[x]]&&x!=ch[1][fa[x]];

		}

	void pushup(int x)

		{

			mx[x]=max(max(mx[ch[0][x]],mx[ch[1][x]]),w[x]);

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

		}

	void rotate(int x)

		{

			int y=fa[x],z=fa[y],c=son(x);

			ch[c][y]=ch[c^1][x];if (ch[c][y]) fa[ch[c][y]]=y;

			fa[x]=z;if (!isroot(y)) ch[son(y)][z]=x;

			ch[c^1][x]=y;fa[y]=x;pushup(y);

		}

	void splay(int x)

		{

			for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

				if (!isroot(y)) son(x)^son(y)?rotate(x):rotate(y);

			pushup(x);

		}

	void access(int x)

		{

			for (int y=0;x;y=x,x=fa[x])

			{

				splay(x);if (ch[1][x]) S[x].insert(mx[ch[1][x]]);

				ch[1][x]=y;if (ch[1][x]) S[x].erase(mx[ch[1][x]]);

				pushup(x);

			}

		}

	int findroot(int x)

		{

			access(x);splay(x);

			while (ch[0][x]) x=ch[0][x];

			splay(x);return x;

		}

	void link(int x,int y)

		{

			if (!y) return;

			access(y);splay(y);splay(x);

			fa[x]=y;S[y].insert(mx[x]);pushup(y);

		}

	void cut(int x,int y)

		{

			if (!y) return;

			access(x);splay(x);

			ch[0][x]=fa[ch[0][x]]=0;pushup(x);

		}

}T[2];

void dfs(int u,int f)

{

	for (int i=0,sz=G[u].size();i<sz;++i)

	{

		int v=G[u][i];if (v==f) continue;

		T[col[v]].link(v,u);fa[v]=u;

		dfs(v,u);

	}

}

int main()

{

	n=gi();

	for (int i=1;i<n;++i)

	{

		int u=gi(),v=gi();

		G[u].push_back(v);G[v].push_back(u);

	}

	for (int i=1;i<=n;++i) col[i]=gi();

	for (int i=1;i<=n;++i) w[i]=gi();

	T[0].mx[0]=T[1].mx[0]=-2147483647;

	dfs(1,0);m=gi();

	while (m--)

	{

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

		if (!opt){

			T[col[u]].access(u);int ff=T[col[u]].findroot(u);

			if (col[ff]==col[u]) printf("%d\n",T[col[u]].mx[ff]);

			else printf("%d\n",T[col[u]].mx[T[col[u]].ch[1][T[col[u]].findroot(u)]]);

		}

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

		else{

			T[col[u]].access(u);T[col[u]].splay(u);

			w[u]=gi();T[col[u]].pushup(u);

		}

	}

	return 0;

}

巴特西

[SP16580]QTREE7

题意

sol

code

最新文章

热门文章