BZOJ 1954 Pku3764 The xor-longest Path

题目大意

给你一棵树，边有边权，求一条路径，使得其上的边的异或和最大。

首先看到这题第一个想到的就是求出根到每个节点的路径异或和，之后一条链的异或和就是起点和终点的到根的异或和的异或值。

（我看成点权了……懵逼了半个小时Orz

之后题目就变成了选出两个数使得他们的异或值最大。

这是一道经典的Trie树问题……每次拿着现有的在Trie树上遍历，如果有更优的就走更优的，毕竟1000(2)>0111(2).

#include <cstdio>
#include <algorithm>
using namespace std;
int n,pts=1,sum[100010],c[3100010][2],ans;
int to[200010],nxt[200010],val[200010],head[100010],tot;
inline void ae(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;}
void dfs(int pos,int pre)
{
	int i;
	for(i=head[pos];i;i=nxt[i]) if(to[i]!=pre) sum[to[i]]=sum[pos]^val[i],dfs(to[i],pos);
}
void insert(int x)
{
	int pos,res,i;
	pos=1,res=0;
	for(i=30;~i;--i)
	{
		if(x&(1<<i))
		{
			if(c[pos][0]) res|=1<<i,pos=c[pos][0];
			else if(c[pos][1]) pos=c[pos][1];
			else res|=1<<i;
		}
		else
		{
			if(c[pos][1]) res|=1<<i,pos=c[pos][1];
			else if(c[pos][0]) pos=c[pos][0];
		}
	}
	ans=max(ans,res);
	pos=1;
	for(i=30;~i;--i)
	{
		if(!c[pos][(x&(1<<i))!=0]) c[pos][(x&(1<<i))!=0]=++pts;
		pos=c[pos][(x&(1<<i))!=0];
	}
}
int main()
{
	int i,x,y,z;
	scanf("%d",&n);
	for(i=2;i<=n;++i) scanf("%d%d%d",&x,&y,&z),ae(x,y,z),ae(y,x,z);
	dfs(1,0);
	for(i=1;i<=n;++i) insert(sum[i]);
	printf("%d\n",ans);
	return 0;
}