「一本通 2.3 练习 5」The Xor-longest Path

形式化题目

给定一棵 $n$ 个点的带权树，点编号从 $1$ 到 $n$ ，共 $n-1$ 条边；边 $(u, v)$ 的权为 $w$ 。树上任意两点之间有唯一简单路径，定义这条路径的长度为路径上所有边权按位异或：

\mathrm{xor}(u, v) = \bigoplus_{e \in \mathrm{path}(u, v)} w_e .

求所有点对路径长度的最大值 $\max\limits_{1 \leqslant u < v \leqslant n} \mathrm{xor}(u, v)$ 。

约束： $1 \leqslant n \leqslant 10^5$ ，边权 $0 \leqslant w < 2^{31}$ （实测数据最大 $2147400037$ ）。

样例

下图为样例的树，边标注权值：

graph TD
    n1 ---|"w=3"| n2
    n2 ---|"w=4"| n3
    n2 ---|"w=6"| n4

最长的异或和路径是 $1 \to 2 \to 3$ ，长度 $3 \oplus 4 = 7$ ，与样例输出一致。注意 $1 \to 3$ 与 $2 \to 3$ 等路径的候选值都更小，穷举所有点对共 $\binom{4}{2} = 6$ 条路径即可验证。

正解

思路

朴素做法是枚举点对再逐边求异或；即使预处理 LCA 把"走路"压到 $O(1)$ ，候选仍是全部 $\binom{n}{2}$ 个点对， $n = 10^5$ 时约 $5 \times 10^9$ 次异或，必然超时。瓶颈在于"路径"这个对象天然有 $O(n^2)$ 条——要优化，先得把一条路径塌缩成更小的东西。

观察一：树上前缀异或，路径只由端点决定。 任选根（取点 1），记

d[u] = \text{根到 } u \text{ 的路径上所有边权的异或和}.

从根走到 $u$ 再走到 $v$ ，走过的边恰好是"根 $\to u$ "与"根 $\to v$ "的对称差：公共部分（根 $\to \mathrm{lca}(u,v)$ 段）每条边在异或里出现两次，而 $x \oplus x = 0$ ，恰好消去。于是

\mathrm{xor}(u, v) = d[u] \oplus d[v].

这样"全部 $O(n^2)$ 条路径"就变成"全部点对的 $d$ 值异或"，而 $d$ 数组只需从根做一次遍历。下表是样例的 $d$ 值（由 viz_render.py 生成）：

点	根到该点的边权序列	$d$ 值
1	（根，空路径）	0
2	3	3
3	3 ⊕ 4	7
4	3 ⊕ 6	5

表里 $d[1] \oplus d[3] = 0 \oplus 7 = 7$ 正是样例答案——路径 $1 \to 2 \to 3$ 的异或被完整地搬到了两个端点的 $d$ 值上。于是问题变成：给定 $n$ 个数，求异或最大的一对。

观察二：最大异或对，01 字典树贪心。 这一步即上一题 roj-1472 「一本通 2.3 例 2」The XOR Largest Pair 的结论。比较两个异或值从最高位开始：第 $k$ 位的收益 $2^k$ 严格大于所有低位收益之和 $\sum_{i<k} 2^i$ ，所以"该位能取 $1$ 就一定先取 $1$ "。把每个 $d$ 看成 31 位（bit 30…0）的 01 串，按高位到低位插入01 字典树；查询 $x$ 时从根逐层下降：

该位想走的反向边（与 $x$ 位相反的分支）存在，就走过去——本位异或锁定为 $1$ ，由高位优先这不可能被反超；
反向边不存在，说明所有候选在这一位都与 $x$ 同向，只能走同向边，本位异或为 $0$ 。

每层走进子树后，剩余候选恰好是"前缀已满足"的数，决策互不干扰，所以逐位贪心是独立决策；下降终点必是一条真实的根到叶路径，对应某个真实插入的 $d[j]$ ，结果既不高估也不低估。

实现要点（对应 main.py）：

层数取 31 而不是 30：实测最大边权 $2147400037 > 2^{30}$ ，位数必须覆盖值域，否则最高位被截断；固定从第 30 位降到第 0 位， $x = 0$ 也不会提前退出。
先插后查：对每个 $d[x]$ 先 insert 再 max_xor。这允许 $x$ 与自己配对得 $0$ ，但所有异或值都 $\geqslant 0$ ，不改变最大值；同时保证首元素查询时树非空。
平坦存储：结点数上界 $1 + 31n \approx 3.1 \times 10^6$ ，每个结点两个 int32 孩子槽，用 array('i') 存成 trie[2u]、trie[2u+1]，约 25 MB；若用列表套列表，光对象头就会顶破 128 MB 限制。
迭代遍历：树可能退化成 $10^5$ 深的链，用显式栈求 $d$ ，不写递归。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:32
# update_at: 2026-09-30 13:46

import sys
from array import array

BITS = 31  # 实测边权最大 2147400037 < 2^31，字典树固定走 31 层（高位到低位）


def insert(trie: array, x: int) -> None:
    """把 x 插入 01 字典树：trie[2*node+bit] 是该节点第 bit 位的孩子下标，-1 表示空。"""
    node = 0
    for b in range(BITS - 1, -1, -1):
        bit = x >> b & 1
        child = trie[node << 1 | bit]
        if child < 0:
            child = len(trie) >> 1            # 新节点编号 = 当前节点总数
            trie[node << 1 | bit] = child
            trie.extend((-1, -1))             # 给新节点预留两个孩子槽
        node = child


def max_xor(trie: array, x: int) -> int:
    """在 01 字典树里贪心走每一位：能取反就取反，返回与 x 异或的最大值。"""
    node, ans = 0, 0
    for b in range(BITS - 1, -1, -1):
        bit = x >> b & 1
        other = trie[node << 1 | 1 - bit]  # 走"这一位不同"的分支，本位异或得 1
        if other >= 0:
            node = other
            ans |= 1 << b
        else:
            node = trie[node << 1 | bit]  # 只剩同位分支，本位异或得 0
    return ans


def prefix_xors(g: list[list[tuple[int, int]]], root: int) -> list[int]:
    """求根到每个点的边权异或和 d（d[u]^d[v] 即 u→v 路径异或和），按遍历序返回。"""
    d: list[int] = []
    stack: list[tuple[int, int | None, int]] = [(root, None, 0)]  # (点, 父点, 累计异或和)；迭代 DFS 防止链状树递归爆栈
    while stack:
        u, parent, acc = stack.pop()
        d.append(acc)
        for v, w in g[u]:
            if v != parent:
                stack.append((v, u, acc ^ w))
    return d


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    g: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = next(data), next(data), next(data)
        g[u].append((v, w))
        g[v].append((u, w))

    # d[u]^d[v] 恰好等于 u→v 路径异或和，故答案 = 任意两点 d 的最大异或对
    d = prefix_xors(g, 1)

    trie = array("i", (-1, -1))  # 节点 0 为根
    ans = 0
    for x in d:
        insert(trie, x)
        # 插入后查询允许走到自己（x^x=0），不改变最大值，还避开了空树查询
        ans = max(ans, max_xor(trie, x))

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:27
 * update_at: 2026-10-05 03:27
 */
// 树上最长异或路径：d[u] = 根到 u 的边权异或和，则 u->v 路径异或 = d[u]^d[v]，
// 问题变成 n 个数里求最大异或对，用 01 字典树逐位贪心，O(31n)。

#include <cstdio>

typedef long long ll;

const int MAXN = 100005;      // 点数上限
const int MAXNODE = MAXN * 32; // 字典树结点数上界：1 + 31n
const int BITS = 31;          // 边权 < 2^31，字典树走 31 层（第 30 位到第 0 位）

// 链式前向星存树
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], wei[2 * MAXN];
int cnt_edge = 0;

int n;
ll d[MAXN];        // d[u]：根到 u 的路径边权异或和
bool vis[MAXN];    // 迭代 DFS 时标记点是否入过栈

int ch[MAXNODE][2]; // ch[u][b]：结点 u 的第 b 位孩子下标，0 表示空
int node_num = 0;   // 已用结点数，0 号为根

ll ans = 0;

// 加一条无向边
void add_edge(int u, int v, int w) {
    cnt_edge++;
    to[cnt_edge] = v;
    wei[cnt_edge] = w;
    nxt[cnt_edge] = head[u];
    head[u] = cnt_edge;
}

// 迭代 DFS 求根到每个点的边权异或和（树可能退化成链，避免递归爆栈）
void dfs_d() {
    // 栈里依次放：点、父点、累计异或和
    static int stk_node[MAXN], stk_fa[MAXN];
    static ll stk_xor[MAXN];
    int top = 1;
    stk_node[1] = 1;
    stk_fa[1] = 0;
    stk_xor[1] = 0;
    vis[1] = true;
    d[1] = 0;
    while (top > 0) {
        int u = stk_node[top];
        int fa = stk_fa[top];
        ll acc = stk_xor[top];
        top--;
        d[u] = acc;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == fa) continue;
            if (vis[v]) continue; // 父点之外的重复保护（树本来无环，双保险）
            vis[v] = true;
            top++;
            stk_node[top] = v;
            stk_fa[top] = u;
            stk_xor[top] = acc ^ wei[e];
        }
    }
}

// 把 x 按高位到低位插入 01 字典树
void trie_insert(ll x) {
    int u = 0;
    for (int b = BITS - 1; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (ch[u][bit] == 0) {
            node_num++;
            ch[node_num][0] = ch[node_num][1] = 0;
            ch[u][bit] = node_num;
        }
        u = ch[u][bit];
    }
}

// 在字典树里逐位贪心：能走"与 x 这一位相反"的分支就走，本位异或得 1，
// 高位收益大于所有低位之和，所以这样取一定最优；返回与 x 异或的最大值
ll trie_max_xor(ll x) {
    int u = 0;
    ll res = 0;
    for (int b = BITS - 1; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (ch[u][1 - bit] != 0) {
            res |= 1LL << b;
            u = ch[u][1 - bit];
        } else {
            u = ch[u][bit];
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    dfs_d();

    // 先插后查：允许 x 与自己配对（异或为 0），不影响最大值，还保证树非空
    for (int i = 1; i <= n; i++) {
        trie_insert(d[i]);
        ll cur = trie_max_xor(d[i]);
        if (cur > ans) ans = cur;
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度： $O(n + 31n)$ 。求 $d$ 一次遍历 $O(n)$ ；每个 $d$ 值插入、查询各走 31 层，合计约 $6.2 \times 10^6$ 次循环迭代（朴素点对枚举约 $5 \times 10^9$ ，是它的约 800 倍）。与标准 C++ 正解同阶；本地实测最重组约 0.7 s，Python 在 OJ 1000 ms 限时下有 TLE 风险（按仓库约定允许）。
空间复杂度： $O(n + 31n)$ 。建图与 $d$ 数组 $O(n)$ ；字典树平坦 array('i') 约 25 MB，本地含解释器峰值 78 MB，在 128 MB 限制内。
验证：真实测试数据 xor0–xor9 共 10 组，verify.sh 1478 全部输出一致（PASS=10）。

总结

异或的对消性（ $x \oplus x = 0$ ）让路径公共段抵消：路径异或只依赖端点，一次遍历求出根前缀异或 $d$ ， $O(n^2)$ 条路径瞬间变成 $n$ 个数。
于是问题精确落到"序列最大异或对"——字典树章节的 roj-1472 「一本通 2.3 例 2」The XOR Largest Pair，贪心结论原样复用。
01 字典树逐层贪心的合法性来自高位收益大于全部低位之和：能取反向边就取，取不到说明所有候选都同向，没得选。
位数由值域决定：本题 $w < 2^{31}$ 要 31 层；层数不足会静默截断最高位，表现为部分数据答案偏小。
存储结点用平坦 array('i')（两槽一对）把空间压到 25 MB；深链用迭代遍历，避免 Python 递归爆栈。

「一本通 2.3 练习 5」The Xor-longest Path

目录

形式化题目

样例

正解

思路

代码

复杂度

总结