#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/43486733");
}
题意：
多组数据、
给你一颗树，
然后求一条最长异或路径，
异或路径长度定义为两点间简单路径上所有边权的异或和。
题解：
首先无根树转有根树再在树上跑一遍算出每个点到根的异或和。
然后两点间异或路径长度就是a[i]*a[j]。
因为lca之前那一段都被异或了两次搞没了。
然后求个线性基，然后随便搞搞就可以？可以WA了！
因为那么算哪是简单路径啊，或者说，那特喵的是什么玩意啊。
嗯，写个Trie树，然后详情可以看我这篇博客。
诶？这篇博客什么也没说？
好吧，我补个题解：
Trie里面记录每个节点权值的二进制串，
比如5，我们不记录“101”，而是记录“00000……000101”
这样Trie树建好了以后我们枚举一个节点，然后用这个节点在Trie树中找它的最长异或路径长度。
这个时候我们在Trie树上跑，每一位都取反以保证这位尽量是1
然后走不了再取同。
所有最长中取个最大值作为答案
这样就在nlogn时间内得到了解。
详见代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define LOGN 32
#define T 2
#define inf 0x3f3f3f3f
using namespace std;
int src[N],n;
struct Trie
{
int son[N*LOGN][T],cnt;
void init()
{
memset(son,0,sizeof son);
cnt=0;
}
void insert(int a)
{
int i,x=0,alp;
for(i=31;i>=0;i--)
{
alp=(a>>i)&1;
if(!son[x][alp])son[x][alp]=++cnt;
x=son[x][alp];
}
}
int find(int a)
{
int i,x=0,alp;
int ret=0;
for(i=31;i>=0;i--)
{
alp=!((a>>i)&1);
ret<<=1;
if(son[x][alp])
{
x=son[x][alp];
ret++;
}
else x=son[x][!alp];
}
return ret;
}
}trie;
struct KSD
{
int v,len,next;
}e[N<<1];
int head[N],cnt;
void init()
{
cnt=0;
memset(src,0,sizeof src);
memset(head,0,sizeof head);
trie.init();
}
inline void add(int u,int v,int len)
{
e[++cnt].v=v;
e[cnt].len=len;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int x,int p)
{
int i,v;
for(i=head[x];i;i=e[i].next)
{
v=e[i].v;
if(v==p)continue;
src[v]=src[x]^e[i].len;
dfs(v,x);
}
return ;
}
int main()
{
freopen("test.in","r",stdin);
int i,j,k;
int a,b,c;
while(scanf("%d",&n)!=EOF)
{
init();
for(i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a+1,b+1,c),add(b+1,a+1,c);
}
dfs(1,0);
int ans=0;
for(i=1;i<=n;i++)trie.insert(src[i]);
for(i=1;i<=n;i++)ans=max(ans,trie.find(src[i]));
printf("%d\n",ans);
}
return 0;
}