一般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\n",tmp); 88 } 89 return 0; 90 } View Code

?

我們先要判斷?????????? 01110111010

存在否，這樣才能達到最大值

?

轉載于:https://www.cnblogs.com/forgot93/p/4383735.html

總結

以上是生活随笔為你收集整理的codechef Polo the Penguin and the Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。