# 某島

… : "…アッカリ～ン . .. . " .. .
October 5, 2014

## Problem 1008. Hilarity

### Analysis:

Tire + 貪心 。）

（邊表用 vector 會 TLE。）

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

```
//}/* .................................................................................................................................. */

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);
}
}

```