# 高阶扩展：基环上的最优化与代数构造

## 本节目标

完成两种不套路的函数图/基环树转化：把删一条环边后的直径写成环序列区间摘要；把受位置约束的整数直接解释为一条函数图边，并由有向环望文生义地消去总和。

## 前置知识与课前自测

前置：剥叶找环、树直径 DP、函数图、线段树区间合并。

1. 连通 $n$ 点 $n$ 边图中，哪些边删除后仍连通？
2. 两个不同环根的挂树点之间，删去一条环边后的最远距离由哪三部分组成？
3. 若定义 $f(i)=i-a_i$，什么结构会让 $\sum(i-f(i))$ 自动望文生义为 0？

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

1. 唯一环上的边。
2. 两侧挂树高度、环被切成路径后的根间距离。
3. $f$ 的一个有向环。

</details>

## 问题动机

同样是“找到环”，后续可能完全不同：最优化题需要比较每个断环位置，构造题则可能让环上的望文生义直接消去目标量。本节专门训练找环后的第二次建模。

## 精选例题 1：Roads in the Kingdom

### 来源与题意

- VJudge：[CodeForces-835F](https://vjudge.net/problem/CodeForces-835F)
- 原题：[Codeforces 835F](https://codeforces.com/problemset/problem/835/F)
- 难度：2500；考点：加权基环树、树直径、断环成链、可合并摘要

连通无向图有 $n\le2\times10^5$ 个点和恰好 $n$ 条正权边。删一条边后仍须连通，最小化剩余图的直径。

<details><summary>Hint 1</summary>只能删唯一环上的边；先对每个环点求挂树高度 $h_i$ 与挂树内部最大直径。</details>
<details><summary>Hint 2</summary>删边后把环按某个起点展开为链，设环上坐标为 $d_i$。跨挂树直径是 $h_i+h_j+d_j-d_i$（$i&lt;j$）。</details>
<details><summary>Hint 3</summary>一个有序区间只需保存 `left=max(h-d)`、`right=max(h+d)` 与区间内 `best`。</details>
<details><summary>Hint 4</summary>拼接 A+B 时，新跨区间答案是 `A.left+B.right`；把环复制两遍，查询每个长度为环点数的窗口。</details>

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

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

```text
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)
```

[完整 GNU C++17 实现](../../参考实现/09-基环树/CodeForces-835F.cpp)

## 精选例题 2：Subset with Zero Sum

### 来源与题意

- VJudge：[CodeForces-1270G](https://vjudge.net/problem/CodeForces-1270G)
- 原题：[Codeforces 1270G](https://codeforces.com/problemset/problem/1270/G)
- 难度：2700；考点：反向建模、函数图有向环、望文生义和

多组数据总 $n\le10^6$。给 $i-n\le a_i\le i-1$，构造一个非空下标集合使对应 $a_i$ 之和为 0；题目保证存在。

<details><summary>Hint 1</summary>区间保证 $1\le i-a_i\le n$。</details>
<details><summary>Hint 2</summary>令 $f(i)=i-a_i$，每个点恰有一条出边 $i\to f(i)$。</details>
<details><summary>Hint 3</summary>任取函数图有向环 $i_1\to i_2\to\cdots\to i_k\to i_1$。</details>

### Observations、证明与实现

原约束看似只是在保证某个零和子集存在；真正作用是让 `i-a_i` 始终成为合法下标。沿有向环有 $f(i_t)=i_{t+1}$，所以

$$
\sum_t a_{i_t}=\sum_t(i_t-f(i_t))
=\sum_t(i_t-i_{t+1})=0.
$$

任何有限函数图都至少有一个有向环，因此构造必存在。可用入度剥叶删掉所有非环点，再从任一剩余点沿出边一圈输出。每个输出点互异、集合非空，望文生义式证明总和为 0。时间和空间均为 $O(n)$。

```text
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
```

[完整 GNU C++17 实现](../../参考实现/09-基环树/CodeForces-1270G.cpp)

若上下界不能保证 $f(i)$ 落在 $[1,n]$，建图立即失效；若目标和是常数 $C\ne0$，环的望文生义只会给 0，不能直接调整。

## 扩展与联系

第一题的三元摘要是“有顺序的幺半群”雏形，可替换线段树为双栈滑动队列做到线性；第二题则说明函数图不只用于计数，也可承载望文生义和与势能差。

## 总结与自检

两题共同点是先找“唯一环/必有环”，但后续任务完全不同。为什么第一题摘要合并有方向？第二题的下标范围怎样保证出边合法？

## 课后训练建议

先独立完成第二题，再为第一题手推摘要合并式；第一题用 $n\le9$ 枚举删边和全点对距离对拍。卡在第一题 30 分钟后看 Hint 2--3。