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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

## 问题动机

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

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

### 来源与题意

- VJudge：[CodeForces-724G](https://vjudge.net/problem/CodeForces-724G)
- 原题：[Codeforces 724G](https://codeforces.com/problemset/problem/724/G)
- 难度：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$。

<details><summary>Hint 1</summary>在每个连通分量任取生成树，求根到每点的 XOR 势能 $d_v$。</details>
<details><summary>Hint 2</summary>把每条边的 $d_u\oplus d_v\oplus w$ 插入线性基；它们张成所有可绕行环的 XOR。</details>
<details><summary>Hint 3</summary>固定端点后，可达值集合是仿射空间 $(d_u\oplus d_v)+\operatorname{span}(B)$。</details>
<details><summary>Hint 4</summary>若基能改变第 b 位，则所有点对各有一半空间元素该位为 1；否则只看 $d_u,d_v$ 该位是否不同。</details>

## 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)$。

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

```text
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 实现](../../参考实现/10-高斯消元与CRT/CodeForces-724G.cpp)

## 扩展与联系

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

## 实现边界与复盘

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

## 总结与自检

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

## 课后训练建议

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