题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2819

题目分类：小数据结构，DFS序

题意：

给出一棵树，每次修改一个节点，询问一条路径，操作均为异或。

题解：

因为异或的奇怪性质，所以可以随意维护。

考虑每个修改对答案的贡献，只对终点在这个修改的节点的子树中的询问有贡献，可以直接DFS序维护。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
inline int lowbit(int x)
{
	return (x&(-x));
}
struct bit
{
	int a[600000];
	inline void edit(int x,int y)
	{
		while (x<=500010)
		{
			a[x]^=y;
			x+=lowbit(x);
		}
	}
	inline int query(int x)
	{
		int ss=0;
		while (x>0)
		{
			ss^=a[x];
			x-=lowbit(x);
		}
		return ss;
	}
}sgt;
int n,fat[600000][20],dep[600000];
inline void doubling()
{
	for (int i=1;i<=19;i++)
	{
		for (int j=1;j<=n;j++)
		{
			fat[j][i]=fat[fat[j][i-1]][i-1];
		}
	}
}
inline int lca(int x,int y)
{
	if(dep[x]>dep[y])swap(x,y);
	for (int i=19;i>=0;i--)
	{
		if(dep[fat[y][i]]>=dep[x])
		{
			y=fat[y][i];
		}
	}
	if(x==y)return x;
	for (int i=19;i>=0;i--)
	{
		if(fat[x][i]!=fat[y][i])
		{
			x=fat[x][i];
			y=fat[y][i];
		}
	}
	if(x==y)return x;
	return fat[x][0];
}
int ed,st[600000];
struct node
{
	int to,next;
}g[1100000];
inline void add(int x,int y)
{
	ed++;	
	g[ed].to=y;
	g[ed].next=st[x];
	st[x]=ed;
}
int cur,lef[600000],pos[600000],rig[600000];
inline void dfs(int x,int fa)
{
	cur++;
	lef[x]=cur;
	fat[x][0]=fa;
	dep[x]=dep[fa]+1;
	pos[cur]=x;
	for (int i=st[x];i!=0;i=g[i].next)
	{
		if(g[i].to!=fa)
		{
			dfs(g[i].to,x);
		}
	}	
	rig[x]=cur;
}
int m,x1,x2,va[600000];
char str[120];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&va[i]);
	}
	for (int i=1;i<n;i++)
	{
		scanf("%d %d",&x1,&x2);
		add(x1,x2);add(x2,x1);
	}
	dfs(1,0);doubling();
	for (int i=1;i<=n;i++)
	{
		sgt.edit(lef[i],va[i]);
		sgt.edit(rig[i]+1,va[i]);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%s %d %d",str,&x1,&x2);
		if(str[0]=='Q')
		{
			int tmp=lca(x1,x2);
			if((sgt.query(lef[x1])^sgt.query(lef[x2])^va[tmp])!=0)printf("Yes\n");
			else printf("No\n");
		}
		else
		{
			sgt.edit(lef[x1],va[x1]);
			sgt.edit(rig[x1]+1,va[x1]);
			va[x1]=x2;
			sgt.edit(lef[x1],va[x1]);
			sgt.edit(rig[x1]+1,va[x1]);
		}
	}
	return 0;
}