AcWing 144. 最长异或值路径

题目链接：点击这里

因此，我们首先预处理每个节点 $i$i 到根节点的路径上所有边权的异或值 $A_i\ (1 \leq i \leq n)$Ai​ (1≤i≤n)，即对树进行一次深度优先遍历。

所以，问题就变成了从 $A_1 \sim A_n$A1​∼An​ 这n个数中选出两个，使得异或的结果最大，即与 AcWing 143. 最大异或对 此题相同。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n;
int h[N], e[M], c[M], ne[M], cnt;
int a[N], son[3000000][2], idx;

void add(int u, int v, int w)
{
    e[cnt] = v, c[cnt] = w, ne[cnt] = h[u], h[u] = 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 -- )
    {
        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()
{
    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 0; i < n - 1; i ++ )
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);			//无向图 
        add(v, u, w);
    }

    dfs(0, -1, 0);		//选定起点0，连同父结点-1一起传进去（无向图遍历的常用方式） 

    for(int i = 0; i < n; i++)
		insert(a[i]);

    int res = 0;
    for(int i = 0; i < n; i++)
		res = max(res, search(a[i]));

    cout<<res<<endl;

    return 0;
}