题目描述

题目描述
给定一个树，树上的边都具有权值。

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

⊕ 为异或符号。

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

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

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

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

数据范围
1≤n≤1000001≤n≤100000
0≤u,v<n0≤u,v<n
0≤w<231

样例

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

借鉴y总的代码，要求最大路径异或和，首先求出树状图中每个点到根节点路径长度，然后每两个长度异或，找到最大值即可

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2e5+10;
int h[N],e[M],c[M],ne[M],cnt,n;//无向图每条边算两次，h[N]表示树状图节点，e[M]是边的下一个节点，c[M]每条边权重，ne[M]这个节点的父节点；
int son[3000000][2],idx;
int a[N];
void add(int u,int v,int w)
{
    e[cnt]=v,c[cnt]=w,ne[cnt]=h[u],h[u]=cnt++;//cnt遍历每个节点
}
void dfs(int u,int father,int sum)
{
        a[u]=sum;//记录每个节点到到根节点路径长度
    for(int i=h[u];~i;i=ne[i])//循环到根节点结束
    {
        int j=e[i];
        if(j!=father)//避免重复走
        dfs(j,u,sum^c[i]);
    }
}
void insert(int x)
{
    int p=0;
    for(int i=30;~i;i--) //31位<2^31,
    {
        int &s=son[p][x>>i&1];
        if(!s) s=++idx;
        p=s;
    }
}
int search(int x)
{
    int p=0,res=0;
    for(int i=30;~i;i--)
    {
        int s=x>>i&1;
        if(son[p][!s]) 
        {
            res+=1<<i;
            p=son[p][!s];
        }
        else p=son[p][s];
    }

    return res;

}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0,u,v,w;i<n-1;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(0,-1,0);
    for(int i=1;i<n;i++) insert(a[i]);
    int res=0;
    for(int i=1;i<n;i++) 
   res=max(res,search(a[i]));
   cout<<res<<endl;
   return 0;
   }