首先，我们求出树的DFS序（为何是树？要解释？！）
下面说明算法
例：
这棵树的DFS序应该是ABEEFFBCCDGHHIIJJGDA
根据这来建立BIT，显然两个点的最近公共祖先就在这两个点之外某处
如，E到H的路径为：EBADGH
DFS序则为EFFBCCDGH，所有在这个路径上的点都出现一次（LCA除外），所有不在这个路径上的点都出现了0或2次
根据Nim博弈的性质，我们只需要求出对应的区间异或和再异或LCA的值，就能得到答案
居然花了16秒的AC-Code（什么时候我的常数才能小下去？）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;
const int MAXN=500005,MAXM=1000005;
//--Tree
int t[MAXM],next[MAXM],first[MAXN],tote;
int A[MAXN],C[MAXM];
int stack[MAXN],tot;
int begin[MAXN],end[MAXN];
int deep[MAXN];
int anc[MAXN][20];
int n;
//--DFS
void dfs(int s)
{
int x,f,top=0;
begin[stack[++top]=s]=deep[s]=++tot;
while (top)
{
x=stack[top];f=0;
for (int i=first[x];i;i=next[i])
{
if (!begin[t[i]])
{
begin[t[i]]=++tot;
anc[t[i]][0]=x;
deep[t[i]]=deep[x]+1;
stack[++top]=t[i];
first[x]=next[i];
f=1;
break;
}
}
if (!f)
{
end[x]=++tot;
top--;
}
}
}
void ae(int u,int v)
{
tote++;
t[tote]=v;next[tote]=first[u];first[u]=tote;
tote++;
t[tote]=u;next[tote]=first[v];first[v]=tote;
}
int lca(int x,int y)
{
if (deep[x]<deep[y])
swap(x,y);
int k=deep[x]-deep[y],j=0;
while (k)
{
if (k&1)
x=anc[x][j];
j++;k>>=1;
}
if (x==y)
return x;
for (int j=19;j>=0;j--)
if (anc[x][j]!=anc[y][j])
{
x=anc[x][j];
y=anc[y][j];
}
return anc[x][0];
}
//--Work
int lowbit(int x)
{
return x&(-x);
}
void edit(int i)
{
for (int x=begin[i];x<MAXM;x+=lowbit(x))
C[x]^=A[i];
for (int x=end[i];x<MAXM;x+=lowbit(x))
C[x]^=A[i];
}
int query(int i)
{
int ret=0;
for (int x=i;x;x-=lowbit(x))
ret^=C[x];
return ret;
}
int main()
{
int tu,tv;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&A[i]);
for (int i=1;i<n;i++)
{
scanf("%d%d",&tu,&tv);
ae(tu,tv);
}
dfs(1);
for (int i=1;i<=n;i++)
edit(i);
for (int j=1;j<20;j++)
for (int i=1;i<=n;i++)
anc[i][j]=anc[anc[i][j-1]][j-1];
char buf[20];
int m,qa,qb;
scanf("%d",&m);
while (m--)
{
scanf("%s%d%d",buf,&qa,&qb);
if (buf[0]=='Q')
{
if (query(begin[qa])^query(begin[qb])^A[lca(qa,qb)])
printf("Yes\n");
else
printf("No\n");
}else
{
edit(qa);
A[qa]=qb;
edit(qa);
}
}
return 0;
}