lessons/课程/09-基环树/01-剥叶找环与环上统计.md

基环树：剥叶找环、挂树大小与函数图计数

本节目标

识别无向连通 $n$ 点 $n$ 边图与每点出度 1 的函数图结构；用拓扑剥叶找出环，向环根汇总挂树信息，并完成环上独立决策。

前置知识与课前自测

前置：树、拓扑排序、DFS/BFS、计数原理。

1. 连通无向图有 $n$ 点 $n$ 边时恰有几个简单环？
2. 每点出度 1 的弱连通分量为何恰有一个有向环？
3. 反复删除度数 1 的点后，基环树中剩下什么？

答案

1. 恰一个；相对树多出的唯一一条边产生唯一环。 2. 沿出边无限走必重复；两个不同有向环不可能在同一弱连通分量由出度 1 的边连接。 3. 环上点；挂树被从叶到根全部删除。

问题动机与核心知识

基环树（unicyclic graph/pseudotree）的关键不是“像树一样 DFS”，而是先分离唯一破坏树结构的环。无向图用度数剥叶；函数图用入度剥叶。被剥点形成指向环的树，剩余点构成一个或多个环。

剥叶还能顺便做 DP：无向图初始化 size[v]=1，叶子弹出时把大小加给唯一尚未删除邻点，最终每个环点的 size 就是它连同挂树的点数。

实现指南

• 无向剥叶判断 degree==1；孤立点不属于本主题的连通 n 边输入。
• 函数图删除 u 时只需降低 indegree[to[u]]。
• 遍历剩余环要单独 visited，不能依赖原 DFS 父亲。
• 环上 DP 常需“强制第一个选/不选”做两次链 DP，避免首尾状态冲突。

精选例题 1：Mouse Hunt

来源与题意

• CodeForces-1027D Mouse Hunt，难度 1700
• 每个点有代价 $c_i$ 且指向一个点 $a_i$；求打断所有无限追逐环的最小总代价。

Hint 1

每个函数图弱连通分量只有环会导致无限循环。

Hint 2

每个有向环至少处理一个点，且不同环决策独立。

Observations

• 入树上的点最终必进入环，本身不形成新的无限循环。
• 打断一个环任选一个点即可，显然选最小代价。
• 入度剥叶无需递归，适合 $2\times10^5$ 深链。

Editorial 与正确性证明

统计入度并删除入度 0 点；剩余点恰为所有有向环。逐环行走取最小代价并求和。任何可行方案必须触及每个环，否则该环仍无限；每环选择最小点能达到下界，环之间点不重叠，故全局最优。复杂度 $O(n)$。

核心伪代码与附件

queue all vertices with indegree 0
while queue: remove u; decrease indegree[to[u]]
for each unvisited remaining vertex:
    walk its directed cycle and add minimum cost on this cycle

完整 C++17 附件

精选例题 2：Number of Simple Paths

来源与题意

• CodeForces-1454E Number of Simple Paths，难度 2000
• 多组连通无向图，每组 $n$ 点 $n$ 边；统计所有无序点对之间的简单路径总数。

Hint 1

同一挂树根下的两点只有一条简单路径。

Hint 2

挂在不同环点的两点有两条路径，分别走环两侧。

Hint 3

剥叶累计每个环点组大小 $size_i$。

Observations

• 每对点至少一条路径；是否多出一条只取决于它们的环归属是否不同。
• 不必枚举环点对，可用总点对减同组点对。
• 剥叶的大小汇总避免为每个环点重新 DFS 挂树。

Editorial

剥叶并把被删点大小加给尚存邻点，得到环组大小 $s_i$。同组点对贡献 1，异组点对贡献 2。可从所有点对的基础 1 加异组数，等价公式为

$$ n(n-1)-\sum_i\frac{s_i(s_i-1)}2. $$

正确性证明

同组两点之间若绕环另一侧必须重复经过组根，不是简单路径，故仅一条；异组两点到各自环根的树路径唯一，环上两条方向均不重复，故恰两条。所有点恰属一个环组，公式完整且不重。复杂度 $O(n)$。

核心伪代码与附件

size[v] = 1
peel degree-1 vertices; when removing u, add size[u] to its remaining neighbor
answer = n * (n - 1)
for cycle vertex v:
    answer -= size[v] * (size[v] - 1) / 2

完整 C++17 附件

精选例题 3：Directed Roads

来源与题意

• CodeForces-711D Directed Roads，难度 1900
• 每点给一条连接到 $a_i$ 的道路，可任选两个方向之一；统计最终不存在有向环的定向方案，模 $10^9+7$。

Hint 1

无向结构的每个函数图分量是一个环加挂树。

Hint 2

挂树边任意定向都不会单独形成环。

Hint 3

长度 L 的环有 $2^L$ 种定向，只排除两种全顺/全逆的有向环。

Observations、Editorial 与证明

入度剥叶后得到所有环。非环边共 $t$ 条，每条方向任意贡献 $2^t$；每个长度 $L$ 环贡献 $2^L-2$。一个环的混合方向必在某点断开，不能成为有向环；两种一致方向恰形成环。不同分量和边选择独立，相乘即答案。复杂度 $O(n)$。

核心伪代码与附件

peel indegree-0 vertices; removed_count = number peeled
answer = pow(2, removed_count)
for each remaining directed cycle of length L:
    answer *= pow(2, L) - 2

完整 C++17 附件

扩展与联系

基环树最大独立集、直径等问题通常先做挂树 DP，再在环上做断环 DP。若每个分量可能有多环，就不再是基环树，剥叶后剩余的是一般 2-core，环上链式 DP 会失效。

总结与自检

1. 无向度数剥叶与函数图入度剥叶分别留下什么？
2. 挂树大小怎样在剥叶过程中汇总？
3. 异环组点对为什么恰有两条简单路径？
4. 环定向为什么只排除两种？

课后训练建议

用随机小函数图与 Floyd/枚举环核对剩余点；无向题枚举所有简单路径对拍。之后自行推导“基环树最大权独立集”的两次链 DP。