bzoj2819 NIM 樹上兩點間抑或值

       這道題目名字叫NIM實際上和博弈論幾乎一點關系都沒有o(╯□╰)o。題意：帶修改的求樹上兩點間抑或值，不為0輸出"Yes"否則輸出"No"。

       如果我們用f[x]表示x到根節點的抑或值的話題目就轉化為求f[x]^f[y]^a[lca(x,y)]，這樣就給我們修改提供了一種可能，因為修改一個x隻會對x的子樹中的點産生影響，即有f[z]^=v(v為修改的值且z為x子樹中包括x一點）。首先對樹進行一遍dfs，周遊到一個點就記下來。這樣可以預處理以x為根的子樹的起始标号l[x]與結束标号r[x]，l[x]即為x的編号，記一個數組t[x]。那麼如果要修改x為v，隻要将t[l[x]]先抑或a[x]再抑或v，t[r[x]+1]先抑或a[x]再抑或v，最後将a[x]作修改即可。那麼如果令f[x]=t[1]^t[2]^...^t[l[x]]，則隻有x子樹作了修改，其餘的都不變。

       這樣就能寫出代碼了，還是很簡單的：

#include<iostream>
#include<cstdio>
#define N 500005
using namespace std;

int n,m,tot,dfsclk,fst[N],pnt[N*2],nxt[N*2];
int bin[20],fa[N][20],d[N],a[N],c[N],l[N],r[N];
int read(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x;
}
void add(int aa,int bb){
	pnt[++tot]=bb; nxt[tot]=fst[aa]; fst[aa]=tot;
}
void dfs(int x){
	int i,p; l[x]=++dfsclk;
	for (i=1; bin[i]<=d[x]; i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	for (p=fst[x]; p; p=nxt[p]){
		int y=pnt[p]; if (y==fa[x][0]) continue;
		d[y]=d[x]+1; fa[y][0]=x; dfs(y);
	}
	r[x]=dfsclk;
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int tmp=d[x]-d[y],i;
	for (i=0; i<=18; i++) if (tmp&bin[i]) x=fa[x][i];
	for (i=18; i>=0; i--) if (fa[x][i]!=fa[y][i]){
		x=fa[x][i]; y=fa[y][i];
	}
	return (x==y)?x:fa[x][0];
}
void mdy(int x,int y){
	int i; for (i=x; i<=n; i+=i&(-i)) c[i]^=y;
}
int getnim(int x){
	int sum=0,i; for (i=x; i; i-=i&(-i)) sum^=c[i]; return sum;
}
int main(){
	n=read(); int i;
	for (i=1; i<=n; i++) a[i]=read();
	for (i=1; i<n; i++){
		int x=read(),y=read(); add(x,y); add(y,x);
	}
	bin[0]=1; for (i=1; i<=19; i++) bin[i]=bin[i-1]<<1;
	dfs(1); int m=read(); char ch;
	for (i=1; i<=n; i++){ mdy(l[i],a[i]); mdy(r[i]+1,a[i]); }
	while (m--){
		ch=getchar(); while (ch!='Q' && ch!='C') ch=getchar();
		if (ch=='C'){
			int x=read(),y=read();
			mdy(l[x],a[x]^y); mdy(r[x]+1,a[x]^y); a[x]=y;
		} else{
			int x=read(),y=read(),tmp=lca(x,y);
			puts((getnim(l[x])^getnim(l[y])^a[tmp])?"Yes":"No");
		}
	}
	return 0;
}
           

by lych

2015.12.5