首页 > 代码库 > BZOJ1954 Pku3764 The xor-longest Path

BZOJ1954 Pku3764 The xor-longest Path

2024-08-09 02:42:37   218人阅读

"trie的经典应用" -- by hzwer

我们把每个点到根的xor值记下来，然后找出两个xor值最大的即可（因为(a ^ c) ^ (b ^ c) = a ^ b）

于是用trie把每个数的二进制位记下来，每次query的时候利用贪心，试图走到另一个儿子即可。

 

技术分享
  1 /**************************************************************  2     Problem: 1954  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:360 ms  7     Memory:27368 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 100005; 15   16 struct edge { 17     int next, to, v; 18     edge() {} 19     edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 20 } e[N << 1]; 21   22 int first[N], tot; 23   24 struct trie_node { 25     int son[2]; 26 } t[3000005]; 27   28 int cnt_trie = 1, root = 1; 29   30 int n, ans; 31 int v[N], a[40]; 32   33 inline int read() { 34     int x = 0, sgn = 1; 35     char ch = getchar(); 36     while (ch < ‘0‘ || ‘9‘ < ch) { 37         if (ch == ‘-‘) sgn = -1; 38         ch = getchar(); 39     } 40     while (‘0‘ <= ch && ch <= ‘9‘) { 41         x = x * 10 + ch - ‘0‘; 42         ch = getchar(); 43     } 44     return sgn * x; 45 } 46   47 void Add_Edges(int x, int y, int z) { 48     e[++tot] = edge(first[x], y, z), first[x] = tot; 49     e[++tot] = edge(first[y], x, z), first[y] = tot; 50 } 51   52 void dfs(int p, int fa) { 53     int x, y; 54     for (x = first[p]; x; x = e[x].next) 55         if ((y = e[x].to) != fa) { 56             v[y] = v[p] ^ e[x].v; 57             dfs(y, p); 58         } 59 } 60   61 void insert(int x) { 62     int now, i, cnt_a = 0; 63     for (i = 0; i <= 30; ++i) 64         a[i] = x & 1, x >>= 1; 65     reverse(a, a + 31); 66     now = root; 67     for (i = 0; i <= 30; ++i) { 68         if (!t[now].son[a[i]]) t[now].son[a[i]] = ++cnt_trie; 69         now = t[now].son[a[i]]; 70     } 71 } 72   73 int query(int x) { 74     int now, i, cnt_a = 0, res = 0; 75     for (i = 0; i <= 30; ++i) 76         a[i] = x & 1, x >>= 1; 77     reverse(a, a + 31); 78     now = root; 79     for (i = 0; i <= 30; ++i) { 80         if (t[now].son[!a[i]]) now = t[now].son[!a[i]], res += (1 << 30 - i); 81         else now = t[now].son[a[i]]; 82     } 83     return res; 84 } 85   86 int main() { 87     int i, x, y, z;  88     n = read(); 89     for (i = 1; i < n; ++i) { 90         x = read(), y = read(), z = read(); 91         Add_Edges(x, y, z); 92     } 93     dfs(1, 0); 94     for (i = 1; i <= n; ++i) 95         insert(v[i]); 96     for (i = 1; i <= n; ++i) 97         ans = max(ans, query(v[i])); 98     printf("%d\n", ans); 99     return 0;100 }
View Code

 

BZOJ1954 Pku3764 The xor-longest Path


联系
我们