## Problem 1008. Hilarity

### Brief description:

給定一顆邊權樹，求一條路徑，最大化異或和。

### Analysis:

Tire + 貪心 。）

（邊表用 vector 會 TLE。）

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2815893

See also http://www.codechef.com/viewsolution/4993836

//}/* .................................................................................................................................. */ const int N = int(1e5) + 9, LV = 31; int n; void _r(int &x){ x=reverse_bits(x); x>>=1; } namespace T{ int trans[N*LV][2]; int nn; int new_node(){ RST(trans[nn]); return nn++; } #define v trans[u] void Insert(int x){ _r(x); int u = 0; REP(i, LV){ int c = x & 1; x >>= 1; if (!v) v = new_node(); u = v; } } int Query(int x){ int z = 0, u = 0; _r(x); REP(i, LV){ int c = (x & 1) ^ 1; x >>= 1; z <<= 1; if (!v) c ^= 1; else z |= 1; u = v; } return z; } void Init(){ nn = 0; new_node(); } }; #define aa to[i^1] #define bb to[i] #define v bb #define w ww[i/2] const int M = N*2; int hd[N], suc[M], to[M], ww[N]; int Xor[N], maxXor; void dfs(int u = 0, int p = -1){ T::Insert(Xor[u]); checkMax(maxXor, T::Query(Xor[u])); REP_G(i, u) if (v != p){ Xor[v] = Xor[u] ^ w; dfs(v, u); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif while (~scanf("%d", &n)){ fill(hd, hd+n, 0); FOR_C(i, 2, n<<1){ RD(aa, bb, w); suc[i] = hd[aa], hd[aa] = i++; suc[i] = hd[aa], hd[aa] = i; } maxXor = 0; T::Init(); dfs(); OT(maxXor); } }