02-高阶扩展-删环边直径与代数构造.md 6.0 KB
高阶扩展：基环上的最优化与代数构造
本节目标
完成两种不套路的函数图/基环树转化：把删一条环边后的直径写成环序列区间摘要；把受位置约束的整数直接解释为一条函数图边，并由有向环望文生义地消去总和。
前置知识与课前自测
前置：剥叶找环、树直径 DP、函数图、线段树区间合并。
- 连通 $n$ 点 $n$ 边图中，哪些边删除后仍连通？
- 两个不同环根的挂树点之间，删去一条环边后的最远距离由哪三部分组成？
- 若定义 $f(i)=i-a_i$，什么结构会让 $\sum(i-f(i))$ 自动望文生义为 0？
答案
1. 唯一环上的边。 2. 两侧挂树高度、环被切成路径后的根间距离。 3. $f$ 的一个有向环。问题动机
同样是“找到环”，后续可能完全不同：最优化题需要比较每个断环位置，构造题则可能让环上的望文生义直接消去目标量。本节专门训练找环后的第二次建模。
精选例题 1：Roads in the Kingdom
来源与题意
- VJudge：CodeForces-835F
- 原题：Codeforces 835F
- 难度：2500；考点：加权基环树、树直径、断环成链、可合并摘要
连通无向图有 $n\le2\times10^5$ 个点和恰好 $n$ 条正权边。删一条边后仍须连通，最小化剩余图的直径。
Hint 1
只能删唯一环上的边；先对每个环点求挂树高度 $h_i$ 与挂树内部最大直径。Hint 2
删边后把环按某个起点展开为链，设环上坐标为 $d_i$。跨挂树直径是 $h_i+h_j+d_j-d_i$（$i<j$）。Hint 3
一个有序区间只需保存 `left=max(h-d)`、`right=max(h+d)` 与区间内 `best`。Hint 4
拼接 A+B 时，新跨区间答案是 `A.left+B.right`；把环复制两遍，查询每个长度为环点数的窗口。Observations 与 Editorial
剥叶确定环。对每个环根，在不走环边的挂树中做后序 DP：最高向下距离是 $h_i$，两条最大子链之和更新全局 tree_diameter。这个值不受删哪条环边影响。
若删去环边 $(s-1,s)$，剩余环按 $s,s+1,\ldots,s+k-1$ 成为一条加权链。给复制后的环点递增坐标 $d_i$，不同根之间可能形成的最长路径为
$$ \max_{i<j}\bigl((h_i-d_i)+(h_j+d_j)\bigr). $$
对有序段维护三元摘要 $(L,R,B)$：$L=\max(h-d)$，$R=\max(h+d)$，$B$ 是段内合法 $i<j$ 最大值。相邻段合并为
$$ (\max(L_A,L_B),\max(R_A,R_B),\max(B_A,B_B,L_A+R_B)). $$
顺序不能交换，因为跨段对只允许左端点在 A、右端点在 B。在线段树上查询双倍环的每个长度 $k$ 窗口，取最小 $B$，再与挂树内部直径取最大。
正确性与复杂度
任何可删边必在环上；删后任意最短路要么完全位于一棵挂树，要么由“上行到环根 + 环链唯一段 + 下行”构成，两个候选类别完整。摘要按端点所属左右段分类，三项合并恰覆盖且不重复所有 $i<j$。枚举所有旋转窗口等价于枚举所有删边，故最小值正确。
剥叶和树 DP 为 $O(n)$，$k$ 次区间查询为 $O(k\log k)$，空间 $O(n)$。
实现指南、核心伪代码与附件
peel leaves to mark the unique cycle
for every cycle root:
tree DP -> height[root], global tree_diameter
walk cycle in order and duplicate it; build weighted coordinates d
leaf summary at i = (h[i]-d[i], h[i]+d[i], -INF)
for every cut/start s:
cross = query summary on [s, s+k).best
answer = max(tree_diameter, minimum cross over all s)
精选例题 2：Subset with Zero Sum
来源与题意
- VJudge：CodeForces-1270G
- 原题：Codeforces 1270G
- 难度：2700；考点：反向建模、函数图有向环、望文生义和
多组数据总 $n\le10^6$。给 $i-n\le a_i\le i-1$，构造一个非空下标集合使对应 $a_i$ 之和为 0；题目保证存在。
Hint 1
区间保证 $1\le i-a_i\le n$。Hint 2
令 $f(i)=i-a_i$，每个点恰有一条出边 $i\to f(i)$。Hint 3
任取函数图有向环 $i_1\to i_2\to\cdots\to i_k\to i_1$。Observations、证明与实现
原约束看似只是在保证某个零和子集存在；真正作用是让 i-a_i 始终成为合法下标。沿有向环有 $f(it)=i{t+1}$，所以
$$ \sumt a{i_t}=\sum_t(i_t-f(i_t)) =\sum_t(it-i{t+1})=0. $$
任何有限函数图都至少有一个有向环，因此构造必存在。可用入度剥叶删掉所有非环点，再从任一剩余点沿出边一圈输出。每个输出点互异、集合非空，望文生义式证明总和为 0。时间和空间均为 $O(n)$。
f[i] = i - a[i]
peel all indegree-zero vertices in the functional graph f
start from any remaining vertex and follow f until returning
output exactly this directed cycle
若上下界不能保证 $f(i)$ 落在 $[1,n]$，建图立即失效；若目标和是常数 $C\ne0$，环的望文生义只会给 0，不能直接调整。
扩展与联系
第一题的三元摘要是“有顺序的幺半群”雏形，可替换线段树为双栈滑动队列做到线性；第二题则说明函数图不只用于计数，也可承载望文生义和与势能差。
总结与自检
两题共同点是先找“唯一环/必有环”，但后续任务完全不同。为什么第一题摘要合并有方向？第二题的下标范围怎样保证出边合法？
课后训练建议
先独立完成第二题，再为第一题手推摘要合并式；第一题用 $n\le9$ 枚举删边和全点对距离对拍。卡在第一题 30 分钟后看 Hint 2--3。