1 int trie[MX][26],tot=1;
2 bool end[MX];
3 void insert(char *str)
4 {
5 int len=strlen(str),p=1;
6 FOR(k,1,len)
7 {
8 int ch=str[k]-'a';
9 printf("%d ",ch);
10 if(!trie[p][ch])trie[p][ch]=++tot;
11 p=trie[p][ch];
12 }
13 end[p]=true;
14 }
15 bool search(char *str)
16 {
17 int len=strlen(str),p=1;
18 FOR(k,1,len)
19 {
20 p=trie[p][str[k]-'a'];
21 if(p==0) return false;
22 }
23 return end[p];
24 }
3764 @ POJ - xor-leongest Path
跳转原OJ
1 const int u=100010;
2 int ver[2*u],edge[2*u],next[2*u],head[u],v[u],val[u*32],a[u*32][2],f[u];
3 int n,tot,i,ans,x,y,z;
4
5 void add(int x,int y,int z)
6 {
7 ver[++tot]=y; edge[tot]=z; next[tot]=head[x]; head[x]=tot;
8 }
9
10 void dfs(int x)
11 {
12 v[x]=1;
13 for(int i=head[x];i;i=next[i])
14 if(!v[ver[i]])
15 {
16 f[ver[i]]=f[x]^edge[i];
17 dfs(ver[i]);
18 }
19 }
20
21 void ins(int x,int y,int temp)
22 {
23 if(y<0) {val[x]=temp; return;}
24 int z=(temp>>y)&1;
25 if(!a[x][z]) a[x][z]=++tot;
26 ins(a[x][z],y-1,temp);
27 }
28
29 int get(int x,int y,int temp)
30 {
31 if(y<0) return val[x];
32 int z=(temp>>y)&1;
33 if(a[x][z^1]) return get(a[x][z^1],y-1,temp);
34 else return get(a[x][z],y-1,temp);
35 }
36
37 int main()
38 {
39 while(cin>>n)
40 {
41 memset(head,0,sizeof(head));
42 memset(f,0,sizeof(f));
43 memset(v,0,sizeof(v));
44 tot=0;
45 for(i=1;i<n;i++)
46 {
47 scanf("%d%d%d",&x,&y,&z);
48 x++,y++;
49 add(x,y,z); add(y,x,z);
50 }
51 dfs(1); tot=1; ans=0;
52 memset(a,0,sizeof(a));
53 ins(1,30,0);
54 for(i=1;i<=n;i++)
55 {
56 ans=max(ans,f[i]^get(1,30,f[i]));
57 ins(1,30,f[i]);
58 }
59 cout<<ans<<endl;
60 }
61 return 0;
62 }