01-trie,、贪心

题意：

分析：

这是一道01-trie的模板题。
01-trie主要用于处理异或问题。异或问题好像还有一个叫做线性基的常用方法.
我们根据异或的性质(同一个数字异或两次就跟没异或一样)，所以任意两点之间的异或(u,v)等于(u,1)^(1,v)
故，我们可以以1为根节点，求所有其他节点到他的异或和。

然后我们要选择两个点，这两个点(1,u)^(1,v)最大
如何找呢？我们知道异或的机理。同为0异为1
我们一一枚举u，去找v.从u的最高位开始看，找有没有v的当前位和u不一样。
如果不一样的话就选他，然后ans+=1<<i

至于如何去找v，这里我们就要用到01-trie了。
网上有许多交01-trie的去看吧，孩子。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
#define re register
const int max_n = 1e5 + 100;
const int max_m = 2 * max_n;
struct edge{
    int to; int val;
    int next;
}E[max_m];
int cnt = 1;
int head[max_n];
void add(int from, int to,int val) {
    E[cnt].to = to;
    E[cnt].val = val;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int vals[max_n];
void dfs(int u,int fa) {
    for (re int i = head[u];i;i = E[i].next) {
        edge& e = E[i];
        if (e.to == fa)continue;
        vals[e.to] = vals[u] ^ e.val;
        dfs(e.to, u);
    }
}
struct node {
    int childs[2];
}ns[max_n * 31];
int sz = 1;
inline void insert(int num) {
    int u = 1;
    for (re int i = 30;i >= 0;--i) {
        int x = (num & (1 << i)) >> i;
        if (!ns[u].childs[x])
            ns[u].childs[x] = ++sz;
        u = ns[u].childs[x];
    }
}
inline int search(int num) {
    int u = 1;int ans = 0;
    for (re int i = 30;i >= 0;--i) {
        int x = (num & (1 << i)) >> i;
        if (ns[u].childs[!x]) {
            ans += (1 << i);
            u = ns[u].childs[!x];
        }else u = ns[u].childs[x];
    }return ans;
}

int main() {
    ios::sync_with_stdio(0);
    int n;cin >> n;
    for (re int i = 1;i < n;++i) {
        int u, v, w;cin >> u >> v >> w;
        add(u, v, w);add(v, u, w);
    }dfs(1, 0);
    int ans = 0;
    for (re int i = 2;i <= n;++i)insert(vals[i]);
    for (re int i = 2;i <= n;++i)
        ans = max(ans, max(vals[i] ^ 0, search(vals[i])));
    cout << ans << endl;
}