本文共 2374 字，大约阅读时间需要 7 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read #define int long long#define pb push_backusing std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}const int N = 1e5 + 100 ;const int maxsize = 1 << 30 ;struct edge { int to , next , data ; } e[(N<<2)] ;int dis[N] , n , head[N] , tot , ch[N*100][2] , cnt , sum[N*100] , ans ;inline void dfs (int cur , int anc , int dist) { dis[cur] = dist ; for (int i = head[cur] ; i ; i = e[i].next) { int k = e[i].to ; if ( k == anc ) continue ; dfs ( k , cur , dist ^ e[i].data ) ; } return ;}inline void insert (int cur) { int now = 0 ; for (int i = maxsize ; i ; i >>= 1) { bool son = ( ( i & cur ) != 0 ) ? true : false ; if ( ! ch[now][son] ) ch[now][son] = ++ cnt ; now = ch[now][son] ; } ++ sum[now] ; return ;}inline int greedy (int cur) { int now = 0 , res = 0 ; for (int i = maxsize ; i ; i >>= 1) { bool son = ( ( i & cur ) != 0 ) ? false : true ; if ( ! ch[now][son] ) son ^= 1 ; res = ( res << 1 | son ) ; now = ch[now][son] ; } return res ;}inline void build (int u , int v , int w) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].data = w ; head[u] = tot ; return;}signed main (int argc , char * argv[] ) { n = rint () ; rep ( i , 2 , n ) { int u = rint () , v = rint () , w = rint () ; build ( u , v , w ) ; build ( v , u , w ) ; } dfs ( 1 , 0 , 0 ) ; rep ( i , 1 , n ) insert ( dis[i] ) ; rep ( i , 1 , n ) ans = max ( ans , dis[i] ^ greedy ( dis[i] ) ) ; printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ;}
转载于:https://www.cnblogs.com/Equinox-Flower/p/11459884.html