poj3764 The XOR Longest Path【dfs】【Trie树】-白红宇

poj3764 The XOR Longest Path【dfs】【Trie树】

阅读量：5162 次

发布时间：2019-06-13

本文共 3002 字，大约阅读时间需要 10 分钟。

The xor-longest Path

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 10038		Accepted: 2040

Description

In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:

$_{xor}length(p)=\oplus_{e \in p}w(e)$

⊕ is the xor operator.

We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path? 　

Input

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node uand v of length w.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input

40 1 31 2 41 3 6

Sample Output

Hint

The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)

Source

题意：

给一棵带边权的树，想找得到两个点，他们的路径上的权值异或最小。

思路：

首先我们任意找一个作为根，可以用dfs求出其他节点到根的路径的异或，记为xordis

那么对于树上的任意两个节点i, j，i到j的路径的异或和应该是xordis[i] ^ xordis[j]

因为i到j的路径，相当于i到根，根到j，其中重叠的部分，他们的异或值正好是0

因此这道题就变成了找两点异或值最小，https://www.cnblogs.com/wyboooo/p/9824293.html 和这道题就差不多了

最后还需要注意，search找到的最大值是除根以外的，还需要和xordis比较一下，取较大值。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
            8 using namespace std; 9 typedef long long LL; 10 #define inf 0x7f7f7f7f 11 12 int n; 13 const int maxn = 1e5 + 5; 14 struct edge{ 15 int v, w; 16 int nxt; 17 }e[maxn * 2]; 18 int head[maxn], tot = 0; 19 int xordis[maxn]; 20 int trie[maxn * 32 + 5][3], treetot = 1; 21 22 void addedge(int u, int v, int w) 23 { 24 e[tot].v = v; 25 e[tot].w = w; 26 e[tot].nxt = head[u]; 27 head[u] = tot++; 28 e[tot].v = u; 29 e[tot].w = w; 30 e[tot].nxt = head[v]; 31 head[v] = tot++; 32 } 33 34 void dfs(int rt, int fa) 35 { 36 for(int i = head[rt]; i != -1; i = e[i].nxt){ 37 int v = e[i].v; 38 if(v == fa)continue; 39 xordis[v] = xordis[rt] ^ e[i].w; 40 dfs(v, rt); 41 } 42 } 43 44 void init() 45 { 46 memset(head, -1, sizeof(head)); 47 tot = 0; 48 memset(xordis, 0, sizeof(xordis)); 49 memset(trie, 0, sizeof(trie)); 50 } 51 52 void insertt(int x) 53 { 54 int p = 1; 55 for(int i = 30; i >= 0; i--){ 56 int ch = x >> i & 1; 57 if(trie[p][ch] == 0){ 58 trie[p][ch] = ++tot; 59 } 60 p = trie[p][ch]; 61 } 62 } 63 64 int searchh(int x) 65 { 66 int p = 1, ans = 0; 67 for(int i = 30; i >= 0; i--){ 68 int ch = x >> i & 1; 69 if(trie[p][ch ^ 1]){ 70 p = trie[p][ch ^ 1]; 71 ans |= 1 << i; 72 } 73 else{ 74 p = trie[p][ch]; 75 } 76 } 77 return ans; 78 } 79 80 int main() 81 { 82 while(scanf("%d", &n) != EOF){ 83 init(); 84 for(int i = 0; i < n - 1; i++){ 85 int u, v, w; 86 scanf("%d%d%d", &u, &v, &w); 87 addedge(u, v, w); 88 } 89 dfs(0, -1); 90 91 /*for(int i = 0; i < n; i++){ 92 printf("%d\n", xordis[i]); 93 }*/ 94 95 int ans = 0; 96 for(int i = 1; i < n; i++){ 97 insertt(xordis[i]); 98 //cout<
            
             <

转载于:https://www.cnblogs.com/wyboooo/p/9824427.html

你可能感兴趣的文章