分析

在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质 。所以异或两个相同的值时等同于没有异或。所以，树上的简单路径的异或值其实可以看做 。 表示节点 到根的异或和。因为 的值计算了两次，相当于是抵消了。那么题目转化为，在一个序列上找两个节点使他们的异或值最大。显然这个过程需要优化。我们可以考虑 。我们按位由大到小建树。这一类的 有个非常好的性质。在父亲节点就可以知道数的大小关系。这个性质还是比较显然，因为我们是按位由高到低考虑的，那么这一位是 的数，一定大于这一位是 的数。有了这样优美的性质， 就可以维护一些关于值域的题了。所以直接贪心作就好了。时间复杂度为 。

关于01字典树

01 Trie

这个应该是 最常见的形态了。一般的 有按位考虑从高到低的，也有从低到高的。使用方法和处理的问题都有较大的区别。

按位从高到低建树

这一类的 有个非常好的性质。

• 在父亲节点就可以知道数的大小关系。

这个性质还是比较显然，因为我们是按位由高到低考虑的，那么这一位是 的数，一定大于这一位是 的数。有了这样优美的性质， 就可以维护一些关于值域的题了。

一个数字是否出现过

不要跟我说什么 。就考虑用 来考虑这个问题。我们从空节点 开始，按位转移。如果结束节点是被标记过了的，那么表示出现过，则否。时间复杂度为 。其实这个从低到高的建的 也可以维护，但是放在这里显得更自然。

维护整个序列的第 k 小

这个问题解决有非常多的解决方案，这里也不详细展开了。用 来考虑，记录每个节点可以到达的结束节点的个数，记录为 。那么这个 树的用法和权值线段树的用法基本也就一模一样了。考虑走左边还是走右边， 与 分类讨论就行了，比起权值线段树可以免去离散化的过程，但空间开销要大一点了。

可持久化改造

既然 有，类似权值线段树的功能。那么如果可以把 可以持久化，或者用树套一下。权值线段树可以解决的 也可以解决。

考虑什么时候会新建节点，这个只有在插入的时候才会新建节点。那么也只需要，在这个时候再复制节点就可以了。

异或极值

这里讨论最大值。一个数和一个序列中一个数的异或最大值是多少？要支持询问和修改。

• 朴素的单次处理需要 的复杂度，和 的修改。还是考虑平摊一下时间复杂度。

• 考虑把序列插入，构建一个 树。那么在询问时，只需要讨论该数的位是 还是 就行了。这样就需要 的预处理， 的询问和修改。

按位从到高位建树

这个按位从低到高的建树，也有一个很棒的性质，非常好维护异或和。

每一个节点保存该 树的异或和。那么在父亲信息合并时。就可以很自然的写出这样的代码，要记住 的最后一层其实是没有信息的，所以要把位数限制开高一点。

序列权值+1

今年的省选就考了这样一道题。 除开合并儿子信息，那么需要维护一下序列权值 的操作。按 的奇妙做法，只需要 ，其实这个还是比较好理解的。对于每个数的操作，我们都是要从低到高找到第一个不为 的位置。然后把这一位改成 ，后面的全部改为 。那么只需要这样递归处理就行了。

Trie 合并

由上一道题延伸出来的知识点，其实适用于所有 树。操作方法也比较简单，类似于线段树合并。

代码

#include<bits/stdc++.h>
using namespace std;
const int M = 1000011,N = 1e5 + 10;
int read(){
    int x;scanf("%d",&x);return x;
}
vector<int> G[N],W[N];
int n,dis[N],ch[M][2],size,val[M];
void Dfs(int x,int fa){
    for(int i = 0;i < G[x].size();i++)
    {
        int y = G[x][i];
        if(y == fa) continue;
        dis[y] = dis[x] ^ W[x][i];
        Dfs(y,x);
    }
}
void Insert(int x)
{
    int u = 0;
    for(int i = 30;i >= 0;i--)
    {
        int v = (x>>i)&1;
        if(!ch[u][v]){
            ch[u][v] = ++size;
        }
        u = ch[u][v];
    }
    val[u] = x;
}
int AskXor(int x)
{
    int u = 0;
    for(int i = 30;i >= 0;i--)
    {
        int v = (x>>i)&1;
        if(ch[u][v^1]) u = ch[u][v^1];
        else u = ch[u][v];
    }
    return val[u];
}
int main()
{
    n = read();
    for(int i = 1;i < n;i++)
    {
        int a = read(),b = read(),c = read();
        G[a].push_back(b);W[a].push_back(c);
        G[b].push_back(a);W[b].push_back(c);
    }
    Dfs(1,0);
    int Ans = 0;
    for(int i = 1;i < n;i++) Insert(dis[i]);
    for(int i = 1;i <= n;i++) Ans = max(Ans,dis[i] ^ AskXor(dis[i]));
    printf("%d\n",Ans);

}