【手动开栈】【dfs序】【树状数组】【Tarjan】bzoj2819 Nim

考虑树状数组区间修改(只对其子树的答案有影响)点查询，每个点记录的是它到根路径上的权值异或和。

答案时query(L)^query(R)^a[lca]。

这种方法在支持区间加法、减法的树上询问的时候可以避免树链剖分。

可能爆栈，考虑手动开栈。(诶诶Tarjan预处理lca的时候怎么没手动开栈？不要在意^_^)

实际上不会爆的。

#include<cstdio>

#include<stack>

#include<algorithm>

#include<queue>

#include<cmath>

#include<vector>

using namespace std;

#define N 500001

typedef pair<int,int> Point;

vector<Point>ask[N];

int n,a[N],b[N],m,ancestor[N];

int en,first[N],next[N<<1],v[N<<1];

int FA[N],rank[N],lcas[N];

void AddEdge(const int &U,const int &V)

{

	v[++en]=V;

	next[en]=first[U];

	first[U]=en;

}

int findroot(int x){return FA[x]==x?x:findroot(FA[x]);}

void Union(int x,int y)

{

    int U=findroot(x);

    int V=findroot(y);

    if(rank[U]<rank[V]) FA[U]=V;

	else

	  {

        FA[V]=U;

        if(rank[U]==rank[V]) ++rank[U];

      }

}

bool vis[N];

void LCA(int U,int Fa)

{

	ancestor[U]=U;

	for(int i=first[U];i;i=next[i])

	  if(v[i]!=Fa)

	    {

	  	  LCA(v[i],U);

	  	  Union(U,v[i]);

          ancestor[findroot(U)]=U;

	    }

	vis[U]=1;

	for(int i=0;i<ask[U].size();i++)

	  if(vis[ask[U][i].first])

	    lcas[ask[U][i].second]=ancestor[findroot(ask[U][i].first)];

}

stack<int>st;

queue<int>q;

int tot,Ls[N],Rs[N],root=1;

void dfs()

{

	st.push(1);

	Ls[1]=++tot;

	b[1]=a[1];

	while(!st.empty())

	  {

	  	int U=st.top(); bool flag=0;

	  	for(int i=first[U];i;i=next[i])

	  	  if(!Ls[v[i]])

	  	    {

	  	      Ls[v[i]]=++tot;

	  	      b[v[i]]=(a[v[i]]^b[U]);

	  	      st.push(v[i]);

	  	      first[U]=next[i];

	  	      flag=1;

	  	      break;

	  	    }

	  	if(!flag)

	  	  {

	  	  	Rs[U]=tot;

	  	  	st.pop();

	  	  }

	  }

}

int d[N];

void add_node(int p,const int &v){for(;p<=n;p+=(p&(-p)))d[p]^=v;}

void add_range(const int &L,const int &R,const int &v){add_node(L,v);if(R!=n)add_node(R+1,v);}

int query(int p){int res=0;for(;p;p-=(p&(-p)))res^=d[p];return res;}

int A[N],B[N]; char op[N][2];

int main()

{

	int x,y;

	scanf("%d",&n);

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

	  {

	  	FA[i]=i;

	  	scanf("%d",&a[i]);

	  }

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

	  {

	  	scanf("%d%d",&x,&y);

	  	AddEdge(x,y);

	  	AddEdge(y,x);

	  }

	scanf("%d",&m);

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

	  {

	  	scanf("%s%d%d",op[i],&A[i],&B[i]);

		if(op[i][0]=='Q')

		  {

		  	ask[A[i]].push_back(make_pair(B[i],i));

		  	ask[B[i]].push_back(make_pair(A[i],i));

		  }

	  }

	LCA(1,0);

	dfs();

	for(int i=1;i<=n;++i) add_range(Ls[i],Ls[i],b[i]);

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

	  if(op[i][0]=='Q') puts((query(Ls[A[i]])^query(Ls[B[i]])^a[lcas[i]])?"Yes":"No");

	  else

	    {

	      add_range(Ls[A[i]],Rs[A[i]],a[A[i]]^B[i]);

	  	  a[A[i]]=B[i];

	    }

	return 0;

}