The XOR-longest Path(树异或路径转字典树)

发现题面很类似这样一个经典问题:

给出一堆数字,再给你一个数,找到那堆数中与这个数异或最大的

这个问题很经典了,直接建立字典树

对于每个数,二进制分解,然后把二进制从高位到低位插入到字典树上

形成一个深度为的字典树,异或最大值就不停的贪心选择走还是走即可

但是树上路径没那么简单了,不再是简单的两数异或......

但是如果处理一个数组,表示根到自己的异或值

那么和的路径异或值不就是吗

因为他们的部分异或了两次,消掉了

这样一来,转化为把插入字典树了

#include <bits/stdc++.h>
using namespace std;
const int maxn=8e6+10;
int n;
struct edge{
    int to,nxt,w;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w){
    d[++cnt]=(edge){v,head[u],w},head[u]=cnt;
}
int dis[maxn];
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to;
        if( v==fa )    continue;
        dis[v]=dis[u]^d[i].w;
        dfs(v,u);
    }
}
int zi[maxn][3],tot;
void insert(int x)
{
    int now=0;
    for(int i=30;i>=0;i--)
    {
        int k=0;
        if( x&(1<<i) )    k=1;
        if( !zi[now][k] )    zi[now][k]=++tot;
        now=zi[now][k];
    }
}
int ask(int x)
{
    int ans=0,now=0;
    for(int i=30;i>=0;i--)
    {
        int k=1;
        if( x&(1<<i) )    k=0;
        if( zi[now][k] )    ans+=(1<<i),now=zi[now][k];
        else    now=zi[now][k^1];
    }
    return ans;
}
int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int l,r,w; cin >> l >> r >> w;
        add(l,r,w); add(r,l,w);
    }
    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,ask(dis[i]) );
    cout << ans;
}