自动搬运

查看原文

来自洛谷，原作者为

	zhengrunzhe 为世界上所有的美好而战

搬运于2025-08-24 22:16:55，当前版本为作者最后更新于2020-02-06 14:01:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

提供一个常数大的一个log解法

出题人把询问分为了一百万个换根和一百万个其余操作，其中前者要求$O(1)$

而我的这个全都是一个log，相当于两百万个问用log的方法解决，也许像树状数组常树小的能过，但我这个lct常数实在是大我最多就卡到90，但这不是问题，主要是提供一个思路。听说有两只log的树状数组开O2艹过去了

由于我不喜欢叫lct，叫$S-T \ Trees$

虚子树叫$dashed$，实链叫$solid$

首先看操作4:路径点权$xorsum$

S-T trees记下点权，维护实链的$xorsum$，$expose$提取路径返回即可

由于是有根树，$expose$需要$evert$换根，记下原本的$root$，$expose$之后把答案存下来，然后$evert(root)$把根换回去再返回答案

接着看操作3:$lca$

s-t trees上找lca有一种做法是先$access(x)$，然后执行$access(y)$，看最后切换虚实的点即$lca$

这种做法是没什么问题的，我这里用的是另一种做法

在$root \ path$上的$non-local \ searching for \ LCA$

一般的树上距离公式:$dis(x,y)=dep_x+dep_y-2dep_{lca}+1$

移项一下:$2dep_{lca}=dep_x+dep_y-dis(x,y)+1$

系数化为1:$dep_{lca}=\frac {dep_x+dep_y-dis(x,y)+1}{2}$

然后我们$access(x)$把x到根的路径提取出来，然后在上面找第$dep_{lca}$个点，即在$root \ path$找排名为$dep_{lca}$的点，类似平衡树上二分即可

操作5:子树$xorsum$

由于$xorsum$是可差分的，切换虚实链是可以通过$xor$掉原实儿子后$xor$新实儿子的，所以我们没有必要去写个toptree，直接s-t trees维护子树信息即可

考虑维护虚子树$xorsum$: $dashed\_sum$

s-t tree上的子树$xorsum$(树簇异或和)表示为$sum$

可以这么维护:$sum=son[0]\rightarrow sum \bigoplus val \bigoplus son[1]\rightarrow sum \bigoplus dashed\_sum$

考虑在$access$的时候把一个点$q$的右儿子$q\rightarrow son[1]$切换为$p$

$q\rightarrow dashed\_sum \bigoplus =q\rightarrow son[1]\rightarrow sum\bigoplus p\rightarrow sum$

异或原右儿子表示把原本的消除，后异或p表示加入p

然后要查询的点$p$的子树异或和$subtree\_sum$就是先$access(p)$，然后输出$p \rightarrow dashed\_sum \bigoplus p \rightarrow val$

操作1:换根+询问所有子树异或和的异或和

不妨先算出原本的所有子树的异或和的异或和，然后再考虑每个操作对答案的影响

3,4,5操作都是没有影响的，现在考虑换根带来的影响

考虑原根为$v$，把根换成$u$的影响，把$v$除到u路径的子树记作$B$，$u$的子树记作$A$，$u,v$的路径记作$[u,v]$，排除端点u,v的记作$(u,v)$，其中$w$为最上面的那个点,$sum_x$表示x的子树异或和

原本的答案记为$sum_u \bigoplus ans(u,v) \bigoplus ans_C \bigoplus sum_v \bigoplus ans_B \bigoplus ans_A$

新答案:$sum_u' \bigoplus ans(u,v)' \bigoplus ans_C \bigoplus sum_v' \bigoplus ans_A \bigoplus ans_B$

$sum_u'=sum_v$(就是整棵树的异或和)

$sum_v'=sum_v \bigoplus sum_w$ (少了到u路径的部分)

考虑$ans(u,v)'$有什么变化

将(u,v)上的所有点按左图由下往上编号$1,2,3,\cdots,|(u,v)|$

特别地,$0=u,|(u,v)|+1=v,|(u,v)|=w$

考虑一个点$k$的子树异或和咋变

首先$k-1$以下的部分倒过来变成$k$的祖先，所以$sum_k\bigoplus=sum_{k-1}$

其次在$k$上方的所有点倒过来在$k$的子树中，所以$sum_k\bigoplus=sum_v \bigoplus sum_k$

然后我们对于所有的$k$串在一起，发生的变化为:

$(sum_0\bigoplus sum_v \bigoplus sum_1) \bigoplus(sum_1 \bigoplus sum_v \bigoplus sum_2)\bigoplus \cdots \bigoplus (sum_{|(u,v)|-1}\bigoplus sum_v \bigoplus sum_{|(u,v)|})$

由于异或有结合律合交换律，所以发现能删去一堆东西

$=sum_0 \bigoplus sum_1 \bigoplus sum_1 \bigoplus sum_2 \bigoplus sum_2 \bigoplus \cdots \bigoplus sum_{|(u,v)|}(\bigoplus sum_v \bigoplus sum_v \bigoplus \cdots \bigoplus sum_v)(|(u,v)| \text {次})$

中间的都可以消掉,最后由于异或偶数个相同的可以消除，所以化为

$sum_u \bigoplus sum_w (\bigoplus sum_v(|(u,v)|\text{为奇数}))$

然后考虑最终答案变了什么

$ans=sum_u \bigoplus ans(u,v) \bigoplus ans_C \bigoplus sum_v \bigoplus ans_B \bigoplus ans_A$

$ans'=sum_u' \bigoplus ans(u,v)' \bigoplus ans_C \bigoplus sum_v' \bigoplus ans_A \bigoplus ans_B$ $ans'=sum_v \bigoplus ans(u,v) \bigoplus sum_u \bigoplus sum_w (\bigoplus sum_v(|(u,v)|\text{为奇数}))\bigoplus ans_C \bigoplus sum_v \bigoplus sum_w \bigoplus ans_A \bigoplus ans_B$ $ans'=sum_u\bigoplus ans(u,v)(\bigoplus sum_v(|(u,v)|\text{为奇数}))\bigoplus ans_A \bigoplus ans_B \bigoplus ans_C$

$ans'\bigoplus ans=sum_v(\bigoplus sum_v(|(u,v)|\text{为奇数}))$

由于$|(u,v)|=dep_u-2$，奇偶性与$dep_u$相同

$ans'=ans(\bigoplus sum_v (dep_u\text{为偶数}))$

s-t trees维护实链长度$solid_size$，$access(u)$一下获取$dep_u$(即rootpath长度即solid_size)，$sum_v$就是整棵树的异或和，在操作2的时候变化

操作2:单点修改

这一个操作也是会影响操作1的答案的，考虑变化了什么

u到根路径上的所有点的子树异或和都消去了原来的点权加上了新的点权

所以直接$access$然后看$dep_u$的奇偶性，是奇数答案就异或上$u\rightarrow val \bigoplus w$

然后把$u\rightarrow val$赋成$w$即可

$O(n \log n+(m+q) \log n)$

#include<cstdio>
template<class type>inline const void read(type &in)
{
	in=0;char ch(getchar());
	while (ch<48||ch>57)ch=getchar();
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
template<class type>inline const void swap(type &a,type &b){const type c(a);a=b;b=c;}
const int N(1e6+10);
namespace Sleator_Tarjan_Trees
{
	struct tree
	{
		bool rev;
		int solid_size,val,dashed_sum,solid_sum,sum;
		tree *son[2],*fa;
		static tree *null;
		void *operator new(size_t size);
		void *operator new[](size_t size);
		inline tree():rev(0),solid_size(0),val(0),dashed_sum(0),solid_sum(0)
		{
			static bool init(0);
			if (!init)
				init=1,
				null=new tree,
				null->son[0]=null->son[1]=null->fa=null;
			son[0]=son[1]=fa=null;
		}
		inline const void pushup()
		{
			solid_size=son[0]->solid_size+1+son[1]->solid_size;
			solid_sum=son[0]->solid_sum^val^son[1]->solid_sum;
			sum=son[0]->sum^val^son[1]->sum^dashed_sum;
		}
		inline const void reverse()
		{
			swap(son[0],son[1]);rev^=1;
		}
		inline const void pushdown()
		{
			if (rev)son[0]->reverse(),son[1]->reverse(),rev=0;
		}
		inline const bool isroot()
		{
			return fa->son[0]!=this&&fa->son[1]!=this;
		}
		inline const bool id()
		{
			return fa->son[1]==this;
		}
		inline const void set(tree *p,const bool &d)
		{
			(son[d]=p)->fa=this;
		}
		inline const void rotate()
		{
			fa->pushdown();pushdown();
			const bool f(id());
			tree *fa(this->fa),*gfa(fa->fa),*q(son[f^1]);
			if (!fa->isroot())gfa->son[fa->id()]=this;
			(son[f^1]=fa)->son[f]=q;
			((q->fa=fa)->fa=this)->fa=gfa;
			fa->pushup();pushup();
		}
		inline const void splay()
		{
			for (pushdown();!isroot();rotate())
				if (!fa->isroot())
					fa->fa->pushdown(),
					(fa->id()^id()?this:fa)->rotate();
		}
	}*root,*node0,*tree::null;
	#define null tree::null
	inline tree *node(const int &x){return node0+x;}
	char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
	inline void *tree::operator new(size_t size){return tail-=size;}
	inline void *tree::operator new[](size_t size){return tail-=size;}
	inline const void access(tree *p)
	{
		p->splay();
		p->dashed_sum^=p->son[1]->sum;
		p->son[1]=null;
		p->pushup();
		for (tree *q(p->fa);q!=null;q=p->fa)
			q->splay(),
			q->dashed_sum^=q->son[1]->sum,
			q->dashed_sum^=(q->son[1]=p)->sum,
			q->pushup(),
			p->rotate();
	}
	inline const void evert(tree *p)
	{
		access(p);p->reverse();
	}
	inline const void expose(tree *p,tree *q)
	{
		evert(p);access(q);
	}
	inline const void link(tree *p,tree *q)
	{
		access(p);evert(q);p->set(q,1);p->pushup();
	}
	inline tree *lca(tree *p,tree *q)
	{
		expose(p,q);
		const int dispq(q->solid_size);
		evert(root);
		access(q);const int depq(q->solid_size);
		access(p);const int depp(p->solid_size);
		int deplca(depp+depq-dispq+1>>1);
		while (p->pushdown(),1)
			if (deplca<=p->son[0]->solid_size)p=p->son[0];
			else if (!(deplca-=p->son[0]->solid_size+1))return p;
				else p=p->son[1];
	}
	inline const int path_sum(tree *p,tree *q)
	{
		expose(p,q);
		const int sum(q->solid_sum);
		evert(root);
		return sum;
	}
	inline const int subtree_sum(tree *p)
	{
		access(p);return p->val^p->dashed_sum;
	}
}using namespace Sleator_Tarjan_Trees;
int n,m,q,ans,sum[N],all;
int head[N],edc,to[N<<1],next[N<<1];
inline const void connect(const int &u,const int &v)
{
	next[++edc]=head[u];to[head[u]=edc]=v;
	next[++edc]=head[v];to[head[v]=edc]=u;
}
inline const void dfs(const int &p,const int &fa)
{
	sum[p]=node(p)->val;
	for (int son,i(head[p]);i;i=next[i])
		if ((son=to[i])^fa)
			dfs(son,p),
			sum[p]^=sum[son],
			link(node(p),node(son));
	ans^=sum[p];
	node(p)->pushup();
}
inline const void modify(const int &x,const int &y)
{
	access(node(x));
	const int dep(node(x)->solid_size);
	if (dep&1)ans^=node(x)->val^y;
	all^=node(x)->val^y;
	node(x)->val=y;
	node(x)->pushup();
}
inline const void makeroot(const int &x)
{
	access(node(x));
	const int dep(node(x)->solid_size);
	if (!(dep&1))ans^=all;
	(root=node(x))->reverse();
}
int main()
{
	read(n);read(m);read(q);
	node0=new tree[n+1];
	for (int i(1);i<=n;i++)read(node(i)->val),all^=node(i)->val;
	for (int u,v,i(1);i<n;i++)read(u),read(v),connect(u,v);
	dfs(1,0);root=node(1);
	for (int opt,x,y,i(1);i<=m+q;i++)
		switch (read(opt),read(x),opt)
		{
			case 1:makeroot(x);printf("%d\n",ans);break;
			case 2:read(y);modify(x,y);break;
			case 3:read(y);printf("%d\n",lca(node(x),node(y))-node0);break;
			case 4:read(y);printf("%d\n",path_sum(node(x),node(y)));break;
			case 5:printf("%d\n",subtree_sum(node(x)));break;
		}
	return 0;
}