「Luogu P4551」最长异或路径

Description

给定一棵 $n\ (1 \leq n \leq 10^5)$ 个点的带权树，求树上最长的异或和路径。$(0 \leq 边权 < 2^{31})$

Source

Solution

$a,b$ 的树上路径异或和其实就是 $a$ 到根的路径异或和与 $b$ 到根的路径异或和的异或值。原因是：根据异或运算的性质 $x \oplus x = 0$ 可知，两个点到根重复的路径会互相抵消为 $0$，对答案不影响。

所以我们可以先用搜索求出每个点到根的路径异或和，然后把这些值插入到 Trie 中，从中选出两点使其异或和最大，这就和另外一题 [LOJ]10050 一样了，不会的话自行阅读，这里不再赘述过程。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5, MAXM = 2e5;
int n, tot, ans, head[MAXN + 5], val[MAXN + 5];
struct Edge {
    int next, to, dis;
} e[MAXM + 5];
struct Trie {
    int tot, ch[MAXN * 31 + 5][2];
    
    inline void insert(int x) {
        int u = 1;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v]) ch[u][v] = ++tot;//新建节点
            u = ch[u][v];
        }
    }
    inline int find(int x) {
        int u = 1, res = 0;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v ^ 1]) u = ch[u][v];//如果没有相反的路，则沿相同的路走 
            else {
                res += 1 << i;//走相反的路
                u = ch[u][v ^ 1];//这一位为 1，累加答案 
            }
        }
        return res;
    }
} tr;

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge) { head[u], v, w };
    head[u] = tot;
}

void dfs(int u, int fa) {
    for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
        if (v == fa) continue;
        val[v] = val[u] ^ w;//预处理出每个节点到根的路径异或和 
        dfs(v, u);
    }
}

int main() {
    read(n);
    for (int u, v, w, i = 1; i < n; ++i) {
        read(u), read(v), read(w);
        addEdge(u, v, w), addEdge(v, u, w);//连无向边 
    }
    dfs(1, 0);
    tr.tot = 1;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, tr.find(val[i]));//查找 x 与 Trie 中已有数的异或最大值 
        tr.insert(val[i]);//把 x 插入到 Trie 中
    }
    write(ans);
    putchar('\n');
    return 0;
}