BZOJ 2819 DFS序+线段树

非递归的DFS写炸了… 交了一个递归版的 过了………..

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=1000050;

int n,nn,q,xx,yy,stk[N],in[N],out[N],top,cnt,tree[N*4];

int first[N],next[N],v[N],tot,num[N],vis[N],fa[N/2][21];

char ch[5];

struct Node{int deep,id;}node[N];

bool cmpdeep(Node a,Node b){return a.deep<b.deep;}

bool cmpid(Node a,Node b){return a.id<b.id;}

void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}

void insert(int l,int r,int pos,int id,int w){

    if(l==r){tree[pos]=w;return;}

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<id)insert(mid+1,r,rson,id,w);

    else insert(l,mid,lson,id,w);

    tree[pos]=tree[lson]^tree[rson];

}

int query(int l,int r,int pos,int L,int R){

    if(l>=L&&r<=R)return tree[pos];

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<L)return query(mid+1,r,rson,L,R);

    else if(mid>=R)return query(l,mid,lson,L,R);

    else return query(l,mid,lson,L,R)^query(mid+1,r,rson,L,R);

}

int lca(int x,int y){

    if(node[x].deep<node[y].deep)swap(x,y);

    for(int i=20;~i;i--)if(node[x].deep-(1<<i)>=node[y].deep)x=fa[x][i];

    if(x==y)return x;

    for(int i=20;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    return fa[x][0];

}

void dfs(int x){

    in[x]=++cnt,insert(0,nn,1,cnt,num[x]);

    for(int i=first[x];~i;i=next[i])if(!vis[v[i]]){

        vis[v[i]]=1,node[v[i]].deep=node[x].deep+1;

        fa[v[i]][0]=x;

        dfs(v[i]);

    }

    out[x]=++cnt,insert(0,nn,1,cnt,num[x]);

}

int main(){

    memset(first,-1,sizeof(first)),vis[1]=1;

    scanf("%d",&n),nn=n*2;

    for(int i=1;i<=n;i++)scanf("%d",&num[i]),node[i].id=i;

    for(int i=1;i<n;i++)scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx);

    node[1].deep=vis[1]=1;

    dfs(1);

    sort(node+1,node+1+n,cmpdeep);

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

        for(int j=1;j<=20;j++)

            fa[node[i].id][j]=fa[fa[node[i].id][j-1]][j-1];

    sort(node+1,node+1+n,cmpid);

    scanf("%d",&q);

    for(int i=1;i<=q;i++){

        scanf("%s",ch);

        if(ch[0]=='Q'){

            scanf("%d%d",&xx,&yy);

            puts(query(0,nn,1,0,in[xx])^query(0,nn,1,0,in[yy])^num[lca(xx,yy)]?"Yes":"No");

        }

        else{

            scanf("%d%d",&xx,&yy),num[xx]=yy;

            insert(0,nn,1,in[xx],yy),insert(0,nn,1,out[xx],yy);

        }

    }

}