记录编号	583083	评测结果	AAAAAAAAAA
题目名称	[POJ 3764]最长异或路径	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.101 s
提交时间	2023-10-04 11:06:37	内存使用	5.42 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int n;
struct node{
    int ver,nx,ed;
}e[N<<1];
int d[N],tot;
class made{
public:
    int son[3];
}a[N<<4];
int hd[N],cnt,ans;
void add(int x,int y,int z){
    tot++;
    e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
}
void dfs(int x,int fa){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver,z = e[i].ed;
        if(y != fa){
           d[y] = d[x] ^ z; 
           dfs(y,x);
        }
    }
}
void insert(int x){
    int p = 0;
    for(int i = 31;i >= 0;i--){
        int u = (x >> i) & 1;
        if(a[p].son[u] == 0)a[p].son[u] = ++cnt;
        p = a[p].son[u];
    }
}
void ask(int x){
    int p = 0,su = 0;
    for(int i = 31;i >= 0;i--){
        int u = (x >> i) & 1;
        if(a[p].son[u^1])su += (1 << i),p = a[p].son[u^1];
        else p = a[p].son[u];
    }
    ans = max(ans,su);
}
int main(){
    freopen("xorlongestpath.in","r",stdin);
    freopen("xorlongestpath.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i < n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(0,-1);
    for(int i = 0;i < n;i++)insert(d[i]);
    for(int i = 0;i < n;i++)ask(d[i]);
    printf("%d\n",ans);
    
    return 0;
    
}