1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 100006
int read( ) {
char ch = ' '; int x = 0;
while( ch < '0' || ch > '9' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) x *= 10 , x += ch - '0' , ch = getchar();
return x;
}
int n;
int head[MAXN] , nxt[MAXN<<1] , to[MAXN<<1] , ww[MAXN << 1] , ecnt = 0;
void ade( int u , int v , int w ) {
nxt[++ecnt] = head[u] , to[ecnt] = v , ww[ecnt] = w , head[u] = ecnt ;
}
int ch[MAXN * 32][2] , cnt = 0;
int getmx( int x ) {
int cur = 0 , res = 0;
for( int dep = 30 ; dep >= 0 ; -- dep )
if( ( x >> dep ) & 1 ) {
if( ch[cur][0] ) cur = ch[cur][0] , res |= ( 1 << dep );
else cur = ch[cur][1];
} else {
if( ch[cur][1] ) cur = ch[cur][1] , res |= ( 1 << dep );
else cur = ch[cur][0];
}
return res;
}
void ins( int x ) {
int cur = 0;
for( int dep = 30 ; dep >= 0 ; -- dep ) {
if( ( x >> dep ) & 1 ) {
if( ch[cur][1] ) cur = ch[cur][1];
else cur = ch[cur][1] = ++ cnt;
} else {
if( ch[cur][0] ) cur = ch[cur][0];
else cur = ch[cur][0] = ++ cnt;
}
}
}
int sdep[MAXN] , res = 0;
void dfs( int x , int fa ) {
res = max( res , getmx( sdep[x] ) ) , ins( sdep[x] );
for( int i = head[x] ; i ; i = nxt[i] ) {
int v = to[i];
if( v == fa ) continue;
sdep[v] = sdep[x] ^ ww[i];
dfs( v , x );
}
}
int main() {
cin >> n;
for( int i = 1 , u , v , w ; i < n ; ++ i )
u = read() , v = read() , w = read() , ade( u , v , w ) , ade( v , u , w );
dfs( 1 , 1 );
cout << res << endl;
}
|
