01-剥叶找环与环上统计.md 10 KB
基环树：剥叶找环、挂树大小与函数图计数
先完成 课前零食：树多长出一条边，熟悉“先剥挂树、后看环”的视角。
本节目标
识别无向连通 $n$ 点 $n$ 边图与每点出度 1 的函数图结构；用拓扑剥叶找出环，向环根汇总挂树信息，并完成环上独立决策。
前置知识与课前自测
前置：树、拓扑排序、DFS/BFS、计数原理。
- 连通无向图有 $n$ 点 $n$ 边时恰有几个简单环？
- 每点出度 1 的弱连通分量为何恰有一个有向环？
- 反复删除度数 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
精选例题 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
精选例题 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
扩展与联系
灵活性实验室：Preserve Distinct（研究导读）
定位与来源
- VJudge：AtCoder-agc062_f Preserve Distinct
- 原题：AtCoder Grand Contest 062 F
- 官方题解：AtCoder Editorial
- 难度：AGC 2000 分；考点：随状态重建函数图、剥叶、环上相等弦的交错结构
有 $N$ 个牌堆、数字 $1..M$，每个数字恰在两个不同牌堆各出现一次，且初始各堆顶数字互异。每次只能删除一个堆顶，并要求删除后所有非空堆顶仍互异；$M\le2\times10^5$，问最多删除多少张牌。
本题保留为“灵活性实验室”，不作为本章后续硬前置。目前只给出经官方题解核对的建模主线，不提供未完成的参考实现，也不把它计作已通过质量门槛的正式例题。
观察 1：状态怎样变成函数图
当前第 $i$ 堆顶为 $a_i$，令 $p_i$ 为数字 $a_i$ 的另一张卡所在牌堆，从 $i$ 向 $p_i$ 连边。每个非空堆恰有一条出边，因此得到动态函数图。观察 2：为什么先找入度 0 的堆
若堆 $i$ 是当前函数图的叶子（入度 0），就没有别的堆顶数字把“另一张卡”放在堆 $i$ 内。它不会成为别人的立即冲突目标，可以从叶侧持续删除并在堆顶变化后更新函数图。反复处理会清掉所有非环部分。观察 3：环为什么还不是普通环 DP
删除某张牌会改变该堆出边，函数图本身随之变化。应截取每个环堆从当前堆顶到“前驱堆顶的另一张卡”之间的片段，再按环序拼成序列 $X$；每个数字在 $X$ 中出现零、一或两次。观察 4：什么结构能打破环
若 $X$ 中有只出现一次的数字，或有两对位置按 $x,\ldots,y,\ldots,x,\ldots,y$ 交错，则可以选择删除顺序打破当前环，之后重新出现叶子并继续剥除。真正阻塞的是所有相等位置对都呈不交错的嵌套结构。不做题也应获得的考虑链
- 朴素状态失败。 用每堆已删张数作状态有指数级组合；只看当前哪些数字冲突又丢失了牌堆内部顺序。
- 第一次换对象。 不追踪全部牌面，而让每个当前堆顶指向其副本所在堆。合法删除的传播关系因此变成函数图的叶与环。
- 剥叶的含义变化。 普通函数图剥叶一次就固定环；本题每次露出新堆顶后必须局部重建出边。算法维护的是“动态障碍图”，不是静态图模板。
- 第二次换对象。 对剩余环，把各堆关键片段拼成循环序列 $X$。问题由牌堆操作转成圆周上相等位置配对的拓扑：单次出现或交错弦能制造破口，完全嵌套才形成最终障碍。
- 最终算法轮廓。 栈可在线判断成对位置是嵌套还是交错，并在线枚举“沿相邻位置、再跳到相等位置”的交替环；给每个候选环累计最终必须保留的牌数，取最小值，再用总牌数减去它。官方题解给出整体 $O(M)$ 的实现方向。
阅读验证与失效边界
- 最小反例是三个堆顶副本首尾相接成环，且下一张恰是前驱堆顶：任何一步都会制造两个相同堆顶，答案可以是 0。
- “叶子就整堆一次删完”是概念上的可交换性结论；实际实现仍要在每次新堆顶出现时更新其指向及相关入度。
- 每个数字恰出现两次，使相等关系成为配对；若出现三次，
另一张卡所在堆不再唯一，函数图与弦匹配模型同时失效。 - 当前缺口是把交替环的栈枚举、候选环权值与原牌堆下标写成一套可对拍的不变量。补齐前，本节只标研究导读，不给伪代码或附件，避免把轮廓误写成可提交算法。
扩展与联系
基环树最大独立集、直径等问题通常先做挂树 DP，再在环上做断环 DP。若每个分量可能有多环，就不再是基环树，剥叶后剩余的是一般 2-core，环上链式 DP 会失效。
总结与自检
- 无向度数剥叶与函数图入度剥叶分别留下什么？
- 挂树大小怎样在剥叶过程中汇总？
- 异环组点对为什么恰有两条简单路径？
- 环定向为什么只排除两种？
课后训练建议
用随机小函数图与 Floyd/枚举环核对剩余点；无向题枚举所有简单路径对拍。之后自行推导“基环树最大权独立集”的两次链 DP。