【维护异或极值】 最长异或路径

传送门

题意

给定一棵树，树上的边都有权值，树上的一条异或路径长度定义为两点间路径上所有边的异或和

• (operatorname{xor} operatorname{length}(p)=oplus_{e in p} w(e))

给定上述的具有(n)个节点的树，求最大的异或和路径的值

数据范围

(egin{array}{l}1 leq n leq 100000 \ 0 leq u, v<n \ 0 leq w<2^{31}end{array})

题解

• 维护每个节点从根到它路径的异或和，求任意两点的路径直接异或两个点到根的异或和即可

  • (dfs)求出每个节点到根的异或和，三个状态当前节点、上一节点、当前异或和

  • 树是无向的，所以要判断一下下一个点是不是等于上一个点

• 异或运算的计算顺序不影响结果

• 如果两个节点从(LCA)开始的公共路径的异或值相同，异或和为(0)，相当于不异或

所以求任意两点间就用字典树维护所有点到根的距离，贪心的从高位开始选择，优先选择高位不同的，
即高位异或后可以得到的值

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)

const int N=1e5+10;

int n;

struct node
{
    int to,ne,w;
}e[N*2];
int h[N],id;
int d[N];
int trie[N*30][2],tot=1;
void add(int u,int v,int w)
{
    e[++id].to = v;
    e[id].w=w;
    e[id].ne=h[u];
    h[u]=id;
}
void insert(int x)
{
    int p=1;
    per(i,0,31)
    {
        int c = x>>i&1;
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
}
int query(int x)
{
    int res=0;
    int p=1;
    per(i,0,31)
    {
        int c=x>>i&1;
        if(trie[p][!c])
        {
            res+=1<<i;
            p=trie[p][!c];
        }
        else p=trie[p][c];
    }
    return res;
}
void dfs(int u,int pre,int sum)
{
    d[u]=sum; 
    for(int i=h[u];i;i=e[i].ne)
        if(e[i].to!=pre) dfs(e[i].to,u,sum^e[i].w);
}

void solve()
{
    int ans=-1e9;
    cin>>n;
    rep(i,0,n)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);add(v,u,w);
    }
    dfs(0,-1,0);

    rep(i,0,n)
    {
        insert(d[i]);
        ans=max(ans,query(d[i]));
    }
    cout<<ans<<endl;
}
int main()
{
    solve();
    return 0;
}