POJ3764 The xor-longest path Trie树

代码写了不到30分钟，改它用了几个小时。先说题意，给你一颗树，边上有权，两点间的路径上的路径的边权抑或起来就是路径的xor值，要求的是最大的这样的路径是多少。讲到树上的两点的xor，一个常用的手段就是随便选一个根，然后深搜记下每个点v到根的xor路径 w[v]，那么两点x,y路径的xor就是w[x]^w[y].

深搜一发，问题转化为给你一个数组a,求a中哪两个数的抑或值最大。解决该问题的方法就是Trie树。

对每个权值由二进制高位到低位插到Trie树里，当要询问对于权值x最大的xor的时候，就需要从树上贪心的去匹配，譬如x的高位是1，那么我们就希望从Trie树上往0走，否则的话我们希望往1走，也就是尽可能使高位最大。这个在Trie树中是很容易实现的。在本题中n个数，最大是2^31-1，所以需要的节点的数量最多可以到到达32n。我们做的时候是询问一个数，插一个数，每次询问的复杂度也是O(32),所以总复杂度是O(32n)

这是Trie树的一个典型应用。

下面说说自己碰到的坑。首先是第一次写Trie树，当我新建结点的时候我忘了对左右儿子设NUll,导致出错。还有一些其余的细节错。最重要的是后来T了不知道多少发。最后发现是被卡邻接表了vector G[maxn]的写法会T, next的那种写法就过了。我想可能是初始化的时候G[i].clear()非常耗时的缘故吧。提醒了我一下邻接表的重要性。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 100050
using namespace std;struct Edge
{
int to;
int w;int next;
Edge(){}
Edge(int ti,int wi):to(ti),w(wi){}
}edges[2*maxn];
int etop;
int w[maxn+50];
int n;
int ans;
int first[maxn+20];void addEdge(int u,int v,int w)
{
Edge &e=edges[etop++];
e.to=v;e.w=w;
e.next=first[u];first[u]=etop-1;
}void dfs(int u,int wht,int fa)
{
w[u]=wht;
for(int i=first[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if(v!=fa){
dfs(v,wht^edges[i].w,u);
}
}
}struct TrieNode
{
TrieNode *next[2];
}T[maxn*32],*Trie;
int top;
int bit[33];
const int maxSize=30;void insert(int x)
{
TrieNode *p=Trie;
for(int i=maxSize;i>=0;--i){
int indice=x&bit[i]? 1:0;
if(p->next[indice]!=NULL){
p=p->next[indice];
}
else{
p->next[indice]=&T[top++];
T[top-1].next[0]=T[top-1].next[1]=NULL;
p=p->next[indice];
}
}
}int find(int x)
{
TrieNode *p=Trie;int ret=0;
for(int i=maxSize;i>=0;--i){
int indice=x&bit[i]? 1:0;
if(p->next[indice^1]!=NULL){
ret+=bit[i];
p=p->next[indice^1];
}
else{
p=p->next[indice];
}}
return ret;
}int main()
{
bit[0]=1;
for(int i=1;i<=31;++i){
bit[i]=bit[i-1]*2;
}
while(cin>>n)
{
int u,v,ww;
memset(first,-1,sizeof(first));etop=0;
for(int i=0;i<n-1;++i){
scanf("%d%d%d",&u,&v,&ww);
addEdge(u,v,ww);
addEdge(v,u,ww);
}
dfs(0,0,-1);top=0;Trie=&T[top++];T[top-1].next[0]=T[top-1].next[1]=NULL;
insert(w[0]);ans=0;
for(int i=1;i<n;++i){
int tmp=find(w[i]);
ans=tmp>ans? tmp:ans;
insert(w[i]);
}
printf("%d\n",ans);
}
return 0;
}