NC50349（The XOR-longest Path ）

感受

思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;        //集合中的数字个数
struct edge{
    int v, nex, w;
}e[maxn << 1];
int ch[32 * maxn][2];               //节点的边信息
int value[32 * maxn];                //节点存储的值
int node_cnt;                       //树中当前节点个数
int f[maxn];
int head[maxn], cnt, n;
inline void init(){                 //树清空
    node_cnt = 1; cnt = 0;
    memset(ch[0], 0, sizeof(ch));
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
void add_edge(int u, int v, int w){
    e[cnt] = (edge){v, head[u], w};
    head[u] = cnt++;
}
inline void Insert(int x){           //在字典树中插入 X
    //和一般字典树的操作相同 将X的二进制插入到字典树中
    int cur = 0;
    for(int i = 30; i >= 0; --i){
        int idx = (x >> i) & 1;
        if(!ch[cur][idx]){
            memset(ch[node_cnt], 0, sizeof(ch[node_cnt]));
            ch[cur][idx] = node_cnt;
            value[node_cnt++] = 0;
        }
        cur = ch[cur][idx];
    }
    value[cur] = x;                 //最后的节点插入value
}
int Query(int x){              //在字典树中查找和X异或的最大值的元素Y 返回Y的值
    int cur = 0;
    for(int i = 30; i >= 0; --i){
        int idx = (x >> i) & 1;
        if(ch[cur][idx ^ 1]) cur = ch[cur][idx ^ 1];
        else cur = ch[cur][idx];
    }
    return value[cur];
}
void dfs(int u, int fa, int x){
    Insert(x); f[u] = x;
    int v; int w;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v; w = e[i].w;
        if(v == fa) continue;
        dfs(v, u, x ^ w);
    }
}
int main(){
    scanf("%d", &n); init();
    int u, v; int w;
    for(int i = 1; i < n; i++){
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w); add_edge(v, u, w);
    }
    dfs(1, 0, 0);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, f[i] ^ Query(f[i]));
    }
    printf("%d\n", ans);
    return 0;
}