题目

分析

1、相似的模版----最大异或对

https://www.acwing.com/activity/content/code/content/9446144/
用于求N个整数，选出两个进行异或，求最大的结果是多少

2、但是本题是求树中两个节点之间唯一路径的各条边的权值的异或结果，求最大结果

3、两个节点之间的边有多条，怎么转成只有两个数异或呢？难点、关键点

4、最终思路

先求出每个点到根节点的路径的异或和，一共有n个数
利用1、中的模版，求出这n个数中，两两进行异或的最大结果

5、难点：怎么求每个点到根节点的路径的异或和

在dfs的过程中求，从根节点出发进行dfs
//补充
在dfs的框架中，可以进行各种关于节点的计算，值既可以存在数组里，也可以用一个变量进行保存等
关键的理解点、难点：
根节点的sum[1]=0，所以根节点不用求
但是我们一开始调用还是从根节点开始dfs(1,-1)
因为求每个节点的sum，如果已经知道了父结点的sum，那只要把父节点的sum再^w，就好了
因此每次的当前节点都是父结点，然后遍历父结点的各个儿子节点，求这些儿子节点的sum
我的错误：
我把视角变成了，每次的当前点是儿子节点，导致不知道怎么得到他的父结点

//递归求出每个节点到根节点的异或和
void dfs(int u,int fa)
{
    //进入dfs时，当前节点的u已经确定了！！！
    //要填写的是，u的各个儿子节点的sum
    for(int i=h[u];i!=-1;i=ne[i]){
        int s=e[i];int c=w[i];
        if(s!=fa){//这个判断便也可以保证每个节点只求了一次
            sum[s]=sum[u]^c;
            dfs(s,u);//递归的求各个儿子节点的
        }
    }
}

6、手写的笔记

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+7;
const int M=N*2;//一条无向边存了两次，所以开的空间要节点的数量*2

int n;
int h[M],e[M],ne[M],w[M],idx;//一开始这里空间只开了N，导致出现re错误。

int sum[N];

int son[N*32][2];//一开始只开了N，导致出现re错误
//son的第一维只有N是不够的，每个二进制位都存了一个节点，因此要乘以二进制位数
int idx1;

void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

//递归求出每个节点到根节点的异或和
void dfs(int u,int fa)
{
    //进入dfs时，当前节点的u已经确定了！！！
    //要填写的是，u的各个儿子节点的sum
    for(int i=h[u];i!=-1;i=ne[i]){
        int s=e[i];int c=w[i];
        if(s!=fa){//这个判断便也可以保证每个节点只求了一次
            sum[s]=sum[u]^c;
            dfs(s,u);//递归的求各个儿子节点的
        }
    }
}

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(son[p][u]==0) son[p][u]=++idx1;
        p=son[p][u];
    }
}

int query(int x)
{
    //找出和x异或最大的数，并返回
    int ans=0;
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(son[p][!u]!=0){
            ans=ans*2+!u;
            p=son[p][!u];
        }else{
            ans=ans*2+u;
            p=son[p][u];
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);//头结点初始化为-1
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);//记得两个方向都要加！！
    }

    //因为是树，所以可以从任意一个节点开始求sum数组
    //头结点的sum[1]=0
    dfs(1,-1);

    int res=-2e9;
    //把sum里的n个数插入到trie树中
    for(int i=1;i<=n;i++){
        insert(sum[i]);
        res=max(res,sum[i]^query(sum[i]));
    }

    printf("%d\n",res);

    return 0;
}