codechef Polo the Penguin and the Tree

一般xor 的题目都是用trie解决。

那这道题是在树上的trie;

首先：从root==1,遍历树得到1到所有节点的xor 值。

然后对于每个点我们把其插入二进制树中。

对于每一个点查找其二进值异或值最大的数依次遍历下来。

注意：边的数量开两倍以上，RE很多次。

find函数具体是这样的：

对于一个书二进值：10001000101

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<string>
 6 #include<cstring>
 7 #include<set>
 8 #include<map>
 9 #include<stdlib.h>
10 
11 #define N  223456
12 using namespace std;
13 struct edge
14 {
15   int v,w,next;
16 }e[N];
17 int tot,nid;
18 int head[N],ans[N];
19 int next[N*30][2];
20 void add(int u,int v,int w)
21 {
22    e[tot].v=v;
23    e[tot].w=w;
24    e[tot].next=head[u];
25    head[u]=tot++;
26 }
27 
28 void dfs(int u,int fa)
29 {
30    for (int i=head[u];i!=-1;i=e[i].next)
31    {
32       int v=e[i].v;
33       if (v==fa) continue;
34       ans[v]=ans[u]^e[i].w;
35       dfs(v,u);
36    }
37 }
38 
39 void insert(int node,int d,int val)
40 {
41    if (d==30)  return;
42    int p=29-d;
43    int c=(val&(1<<p))  ? 1:0;
44 
45    if (next[node][c]==-1) next[node][c]=++nid;
46    insert(next[node][c],d+1,val);
47 }
48 
49 int solve(int node,int d,int val)
50 {
51   if (d==30) return 0;
52   int p=29-d;
53   int c=(val&(1<<p))?0:1;
54 
55   if (next[node][c]!=-1)
56   return (1<<p)+solve(next[node][c],d+1,val);
57 
58   return solve(next[node][!c],d+1,val);
59 }
60 
61 int main()
62 {
63   int T;
64   scanf("%d",&T);
65   while (T--)
66   {
67      int n;
68      scanf("%d",&n);
69      memset(head,-1,sizeof(head));
70      memset(next,-1,sizeof(next));
71      memset(ans,0,sizeof(ans));
72      tot=nid=0;
73      for (int i=1;i<n;i++)
74      {
75         int u,v,w;
76         scanf("%d%d%d",&u,&v,&w);
77         add(u,v,w);
78         add(v,u,w);
79      }
80 
81      dfs(1,-1);
82      for (int i=1;i<=n;i++) insert(0,0,ans[i]);
83      int tmp=0;
84 
85      for (int i=1;i<=n;i++)
86      tmp=max(tmp,solve(0,0,ans[i]));
87      printf("%d
",tmp);
88      }
89      return 0;
90   }

View Code

我们先要判断 01110111010

存在否，这样才能达到最大值