高阶扩展：树势能与 XOR 环空间

本节目标

把允许重复边的路径 XOR 全集分解成“树上固定势能差 + 环空间任意线性组合”，并按二进制位统计所有不同可达值，而不是枚举路径。

前置知识与课前自测

前置：XOR 线性基、DFS 生成树、线性空间计数。

给根到点的树路径 XOR 为 $d_v$，树上 $u\to v$ 的 XOR 是什么？
一条非树边 $(u,v,w)$ 产生的环 XOR 是什么？
一个秩为 $r$ 的 XOR 空间中，某位若能变化，有多少向量该位为 1？

答案

1. $d_u\oplus d_v$。 2. $d_u\oplus d_v\oplus w$。 3. 恰 $2^{r-1}$ 个。

问题动机

允许重复点边后，路径数量无限，但 XOR 只记录每条边经过次数的奇偶。无限走法因此不是更难的搜索，而是在暗示有限维环空间。

精选例题：Xor-matic Number of the Graph

来源与题意

VJudge：CodeForces-724G
原题：Codeforces 724G
难度：2600；考点：生成树势能、XOR 线性基、逐位计数

无向图 $n\le10^5,m\le2\times10^5$，边权 $0\le w\le10^{18}$。路径允许重复点和边。对每个 $u<v$，每一种可由某条 $u\to v$ 路径得到的不同 XOR 值 $s$ 形成三元组 $(u,v,s)$；求所有 $s$ 之和模 $10^9+7$。

Hint 1

在每个连通分量任取生成树，求根到每点的 XOR 势能 $d_v$。

Hint 2

把每条边的 $d_u\oplus d_v\oplus w$ 插入线性基；它们张成所有可绕行环的 XOR。

Hint 3

固定端点后，可达值集合是仿射空间 $(d_u\oplus d_v)+\operatorname{span}(B)$。

Hint 4

若基能改变第 b 位，则所有点对各有一半空间元素该位为 1；否则只看 $d_u,d_v$ 该位是否不同。

Observations 与 Editorial

枚举简单路径已经指数级，允许重复边似乎更大；但同一闭合绕行做两次会 XOR 抵消，所以所有可添加绕行形成 $\mathbb F_2$ 线性空间。

在一个连通分量中任选 DFS 树并令 $d_v$ 为根到 $v$ 的树路 XOR。每条图边给出闭合走法值 $c=d_u\oplus d_v\oplus w$，把全部 $c$ 插入线性基 $B$。任意 $u\to v$ 走法与树路之差是若干闭合走法，故其 XOR 属于

$$ d_u\oplus d_v\oplus\operatorname{span}(B). $$

反过来，每个基本环都可从树路中绕行加入，任意线性组合均可实现，所以该集合完整。

设基秩为 $r$。逐位 $b$：

若某个基向量第 $b$ 位为 1，线性函数“取第 $b$ 位”在空间上非零，恰一半即 $2^{r-1}$ 个空间元素使该位为 1；每个无序点对贡献相同数量。
否则空间所有向量该位为 0，该位由 $d_u\oplus d_v$ 固定。若分量中势能该位为 1 的点数是 $c$，恰有 $c(s-c)$ 个无序点对为 1，每对对应全部 $2^r$ 个空间元素。

各连通分量之间无路径，独立求和。

正确性与复杂度

树势能分解证明每条可达路径值都在上述仿射空间；基本环绕行证明空间每个值都有实际路径，且线性基只保留不同 XOR 值，不会按不同走法重复计数。逐位计数是对有限线性空间上的非零线性函数二等分，故求和准确。

DFS 与扫描边 $O(n+m)$；每个环值插入 60 位线性基，时间 $O(60m+60n)$，空间 $O(n+m)$。

实现指南、核心伪代码与附件

for each connected component:
    DFS tree -> potential d[v]
    basis = empty
    for each component edge (u,v,w):
        basis.insert(d[u] xor d[v] xor w)
    r = basis.rank
    for bit b in 0..59:
        if span(basis) can set bit b:
            count = C(size,2) * 2^(r-1)
        else:
            count = ones_in_d[b] * zeros_in_d[b] * 2^r
        answer += count * 2^b

完整 GNU C++17 实现

扩展与联系

树势能加环空间是无向图 XOR 路径的通用分解；在普通加法最短路中，绕环代价不会按两次抵消，因此不能照搬线性空间模型。

实现边界与复盘

边权到 $10^{18}$，需无符号 64 位并处理位 0..59。
同一环值从无向边两端扫描两次不会改变线性基，但若改为显式列基本环可省常数。
若路径必须简单，任意环空间组合未必能由一条简单路径实现，本模型失效。
识别信号是“允许重复的 XOR 路径”；这通常是在暗示闭合走法只保留奇偶、进入环空间。

总结与自检

为什么固定端点的可达集合是仿射空间而不是线性空间？某一位可变化时为什么恰有一半空间向量为 1？

课后训练建议

用 $n\le7$、小边权，在 (vertex,xor) 状态图上暴力枚举全部可达值对拍。复盘时必须解释“为什么统计的是不同 s，而不是不同路径”。

03-高阶扩展-XOR路径的环空间.md 4.9 KB History Raw