POJ - 3764 01字典树+前缀异或和

异或关于前缀的特性:[u,v]=[1,u]^[1]

注意是路径,假设1为根,prexor[1]不保留数值

/*H E A D*/

int to[maxn<<1],nxt[maxn<<1],cost[maxn<<1],head[maxn],tot;

int prexor[maxn<<1];

void add(int u,int v,int w){

	to[tot]=v;cost[tot]=w;nxt[tot]=head[u];head[u]=tot++;

	swap(u,v);

	to[tot]=v;cost[tot]=w;nxt[tot]=head[u];head[u]=tot++;

}

void init(){

	memset(head,-1,sizeof head);

	prexor[0]=0;

	tot=0;

}

struct Trie{

	int son[maxn<<5][2],b[67],tot;

	void init(){

		memset(son,0,sizeof son);

		tot=0;

	}

	void insert(ll x){

		int now=0;

		rep(i,0,31){

			b[i]=x&1;x>>=1;

		}

		rrep(i,31,0){

			if(!son[now][b[i]]) son[now][b[i]]=++tot;

			now=son[now][b[i]];

		}

	}

	ll find(ll x){

		int now=0;

		ll ans=0;

		rep(i,0,31){

			b[i]=x&1;x>>=1;

		}

		rrep(i,31,0){

			if(son[now][b[i]^1]){

				now=son[now][b[i]^1];

				ans+=(1ll<<i);

			}else{

				now=son[now][b[i]];

			}

		}

		return ans;

	}

}trie;

void dfs(int u,int fa,int lastXor){

	erep(i,u){

		int v=to[i],w=cost[i];

		if(v==fa)continue;

		prexor[v]=lastXor^w;

		dfs(v,u,prexor[v]);

	}

}

int main(){

	int n,u,v,w;

	while(~iin(n)){

		init();

		rep(i,1,n-1){

			u=read();u++;

			v=read();v++;

			w=read();

			add(u,v,w);

		}

		dfs(1,0,0ll);

		trie.init();

		rep(i,1,n) trie.insert(prexor[i]);

		ll ans=0;

		rep(i,1,n) ans=max(ans,trie.find(prexor[i]));

		println(ans);

	}

	return 0;

}

1,v ↩︎

巴特西

POJ - 3764 01字典树+前缀异或和

最新文章

热门文章