题目描述

给定一个树，树上的边都具有权值。

树中一条路径的异或长度被定义为路径上所有边的权值的异或和：

⊕ 为异或符号。

给定上述的具有n个节点的树，你能找到异或长度最大的路径吗？

输入格式
第一行包含整数n，表示树的节点数目。

接下来n-1行，每行包括三个整数u，v，w，表示节点u和节点v之间有一条边权重为w。

输出格式
输出一个整数，表示异或长度最大的路径的最大异或和。

数据范围
$1≤n≤100000$
$0≤u,v<n$
$0≤w<2^{31}$

样例

输入样例：
4
0 1 3
1 2 4
1 3 6
输出样例：
7
样例解释
样例中最长异或值路径应为0->1->2,值为7 (=3 ⊕ 4)

字典树

我们不妨设置一个数组D[x]表示根节点到x的路径上所有的边权的xor值,那么很显然,D[x]=D[father(x)] xor weight(x,father(x)) 也就是D[x节点的父亲]异或上x节点到他父亲的路径.既然如此的话,我们明显发现这道题目D数组是可以通过深度优先搜索求出.

求出所有的D数组,那么x节点到y节点上所有的异或权值就是D[x] xor D[y],换句话来说就是,从根节点到x节点的xor值,和根节点到y节点的xor值,这两条路径重叠了,然后这两条路径就抵消了,因为a xor a=0.本身和本身xor值是0的.

因此我们原问题就转换成为D[1]~D[n]中选择任意两个数,xor的结果值就会变成最大.也就是上一道题目.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int u=100010;
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fic(i,a,b) for(int i=a;i>=b;i--)
int ver[2*u],edge[2*u],Next[2*u],head[u],v[u],val[u*32],a[u*32][2],f[u],trie[2*u][31];
int n,tot,i,ans,x,y,z;
inline int read()//快速读入
{
    char ch=getchar();
    int p=1,q=0;
    for(; ch!='-' && ch<'0' || ch>'9'; ch=getchar());
    if (ch=='-')
        p=-p;
    for(; ch>='0' && ch<='9'; q=q*10+ch-'0',ch=getchar());
    return p*q;
}
inline void add(int x,int y,int z)//链式前项星
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
inline void dfs(int x)
{
    v[x]=1;
    for(int i=head[x]; i; i=Next[i])//枚举x节点所有的路径
        if(!v[ver[i]])
        {
            f[ver[i]]=f[x]^edge[i];
            dfs(ver[i]);
        }
}
void insert(int x,int y,int now)
{
    if(y<0)
    {
        val[x]=now;
        return;
    }
    int z=(now>>y)&1;//取出第y位
    if(!a[x][z]) 
        a[x][z]=++tot;
    insert(a[x][z],y-1,now);
}

int Search(int x,int y,int now)
{
    if(y<0) 
        return val[x];
    int z=(now>>y)&1;//取出第y位
    if(a[x][z^1]) 
        return Search(a[x][z^1],y-1,now);
    else 
        return Search(a[x][z],y-1,now);
}
int main()
{
    n=read();
    for(i=1; i<n; i++)
    {
        x=read();
        y=read();
        z=read();
        x++;
        y++;
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1);
    tot=1;
    ans=0;
    insert(1,30,0);
    for(i=1; i<=n; i++)
    {
        ans=max(ans,f[i]^Search(1,30,f[i]));//选取最大值
        insert(1,30,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}