# 省选联考 2022–2023：树上边界状态与圆方树划分

## 本节目标

学会两种“把原操作换成边界信息”的建模：

1. 一棵子树与外界只有一条边时，用“哪个权值出去、外来权值停在哪里”描述全部操作序列。
2. 一般连通图中的分离条件如何落到圆方树（block-cut tree）上，再用子树中的原点数做 DP。

## 前置知识与课前自测

前置：树形 DP、LCA 与子树、点双连通分量、圆方树、重心。

1. 树上一条边的两侧，在该边被删除前能交换多少次权值？
2. 用一个连通的缩点图连起 $t$ 个最终连通块，为什么每个块至少含一个新边端点？
3. 若 $t\ge2$ 个块的大小差至多 1，它们的大小只可能是哪两个数？

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

1. 恰好一次；删边时两端交换，之后两侧再无通道。
2. 若某最终块没有新边端点，则在收缩后没有新边与它相连，与原图最终连通矛盾。
3. $\lfloor n/t\rfloor$ 与 $\lfloor n/t\rfloor+1$。

</details>

## 问题动机

这两题的原始选择都大到无法枚举：前者是 $(n-1)!$ 种断边次序，后者是 $2^m$ 个边集。真正可压缩的不是“已做了哪些操作”，而是一个已封闭部分与未处理部分的接口。

## 步步式引导

### 第一步：先画分界，再问还能交换什么

对有根树的子树 $sub_x$，它与外界只有 $(x,fa_x)$。无论内部断边顺序多么复杂，这条父边上只会发生一次交换：一个原属于子树的权值离开，一个外来权值进入。

停顿：若记录出去的权值来自 $u$，进来后最终停在 $v$，是否还需要知道每条内部边的时刻？

<details><summary>展开</summary>

不需要。子树内的其他交换可由孩子子树的同类边界状态组合；而外来权值在子树中走过的边数，只由中间交接点和 $v$ 的深度差决定。

</details>

### 第二步：不直接给外来权值定价

外来权值是什么要由祖先状态决定。若把它也放进子树 DP，状态会多一维。因此本题把其路程费用延后到上层结算：DP 只保存已知原权值的费用。

### 第三步：先证明圆方树是正确对象

在《城市建造》中，把 $G-E'$ 的每个连通块收缩。因为收缩图连通，每个块都含新边端点；块数又恰好等于端点数，所以每块恰有一个端点。于是，任意两个被选端点之间的每条路径都不能绕过未选点把它们重新连起。

在一个点双中选两个分属不同最终块的端点，点双内的绕行路径会迫使该点双整体参与分隔。这正是圆方树中“选中方点”的含义。被选方点必须在树上连通，删去它们后的圆点连通块就是原图最终连通块。

## 核心知识

## 精选例题 1：最大权独立集问题

### 来源、题意与范围

- [洛谷-P8294 最大权独立集问题](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P8294)，省选联考 2022。
- $n\le5000$，节点权 $1\le d_i\le10^9$；$c_i<i$，每个父亲最多有两个孩子。
- 每次删一条边，删前两端交换所有题，本次代价是交换的两个权值之和。

<details><summary>Hint 1：不要记录已删边集</summary>看一棵子树与外界的唯一父边，只有两个权值跨过边界。</details>
<details><summary>Hint 2：状态的两个端点</summary>记录子树内哪个原权值被换出，以及外来权值最后停在哪个点。</details>
<details><summary>Hint 3：二叉的用处</summary>一个点周围最多有“父边+两条子边”，它们的相对次序只有常数类型。</details>
<details><summary>Hint 4：把枚举拆成两个最小值</summary>左右子树的中间交接点枚举形如 `min_i(A[u,i]+B[i])`，先对每个端点预处理。</details>

### Observations

1. 任意操作序列的总费用，等于每个原权值乘以它跨过的边数再求和。这删掉了“每次同时给两个端点计价”的时间顺序干扰。
2. 对 $sub_x$，出去与进来的权值各一个。因此用两个原树节点就能表示边界，总状态仅 $O(n^2)$。
3. 若直接枚举左右子树各两个端点，仍会到 $O(n^4)$。转移式可分离成两个共用一个中间端点的最小值；每个有序点对只在其 LCA 处被扫描。

### Editorial

对有序点对 $(u,v)$ 令 $x=LCA(u,v)$。定义 $f[u,v]$ 为：删完 $sub_x$ 内所有边以及 $(x,fa_x)$，把原来在 $u$ 的权值送出子树，并使外来权值最后停在 $v$ 的最小已知代价。外来权值的走路代价不在此状态中结算。

- 叶子：$f[x,x]=d_x$，对应父边上送出 $d_x$。
- 一个孩子 $y$：若 $u=x$，父边先于子边；若 $v=x$，次序相反。两类转移分别是

$$
f[x,v]=\min_{(i,v)\in state(y)}(f[i,v]+d_x),
$$

$$
f[u,x]=\min_{(u,i)\in state(y)}(f[u,i]+d_u+d_x(dep_i-dep_x)).
$$

- 两个孩子：父边在三条相关边中可位于首、中、尾。例如 $u,v$ 分属两个孩子时，次序被强制为“$u$ 侧子边—父边—$v$ 侧子边”，转移可写成

$$
f[u,v]=
\min_i\{f[u,i]+d_x(dep_i-dep_x)+d_u\}
+\min_j f[j,v].
$$

当 $u=x$ 或 $v=x$ 时，另一棵子树会再引入一个中间权值。但式子仍是“对每个中间端点预处理最小值，再扫描当前 LCA 的有序点对”。附件中的 `minimum_one/minimum_two` 正是这两层最小化。

根节点没有父边，因此不建造虚假外来权值，而是按一个/两个孩子单独收口。

### 正确性与复杂度

对子树大小归纳。父边上只有一次交换，所以 $(u,v)$ 完整描述边界；二叉性保证节点周围的断边相对次序均在上述常数分类中。每个孩子状态由归纳假设最优，中间端点取最小便枚举了该次序下的全部可能。反过来，每个转移只拼接互不相交的孩子操作序列和当前节点的边，因此总能构造出合法次序。

有序点对总数 $O(n^2)$，每对只在 LCA 所在转移中常数次参与，时间 $O(n^2)$，空间 $O(n^2)$。$n=5000$ 时内存是主要瓶颈，附件使用一块连续 `int64` 存 DP。

### 核心伪代码与附件

```text
prepare every ordered pair (u,v) in the bucket of LCA(u,v)
solve(x):
    solve children first
    if x is leaf: f[x,x] = weight[x]
    if x has one child:
        scan the child's ordered-pair bucket for the two parent-edge orders
    if x has two children:
        for each of the three parent-edge positions:
            precompute first endpoint minima
            precompute second endpoint minima
            scan ordered pairs whose LCA is x and relax f
close the root separately because it has no parent edge
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P8294.cpp)

### 实现细节

- 权值至 $10^9$，总代价用 64 位；`INF` 要留出加法余量。
- `state[x]` 只保存 LCA 恰为 $x$ 的点对，否则同一点对会在多层被重复扫描。
- $n=1$ 时没有边，答案是 0。
- 附件已用 $n\le8$ 的随机二叉树，枚举全部 $(n-1)!$ 断边顺序对拍。

## 精选例题 2：城市建造

### 来源、题意与范围

- [洛谷-P9167 城市建造](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P9167)，省选联考 2023。
- 给定连通无向图，$n\le10^5,m\le2\times10^5,0\le k\le1$。
- 计数非空边集 $E'$：设 $V'$ 是其端点集，要求 $G-E'$ 恰有 $|V'|$ 个连通块，块大小差至多 $k$。答案模 $998244353$。

<details><summary>Hint 1：先收缩最终连通块</summary>证明每块恰含一个 $V'$ 中顶点。</details>
<details><summary>Hint 2：点双是不可再分的单元</summary>把原图建成圆方树，分隔一组端点对应删去连通的方点区域。</details>
<details><summary>Hint 3：固定小块大小 s</summary>所有块的大小只能是 `s` 或 `s+1`；在圆方树上自底向上判定哪些小子树必须并入当前块。</details>
<details><summary>Hint 4：不要枚举所有 s</summary>`s=floor(n/t)`，不同商只有 $O(\sqrt n)$ 个；$k=0$ 时另只需枚举 n 的约数。</details>

### Observations

1. $G-E'$ 的每块至少有一个新边端点，块数与端点数相同，所以“至少一个”立即加强成“恰好一个”。这删掉了一个块内选多个端点的自由度。
2. 原图中的点双会制造绕路，而圆方树没有环。把“删哪些边”改为“选哪些方点作为连通分隔区”，搜索对象由边集变成树上连通区域。
3. 固定最小块大小 $s$后，大小小于 $s$ 的子树不能单独成块，必须向父亲汇合；大子树则必须在内部完成划分。这使得转移不需背包维度。
4. 选一个原圆点重心作根。任一合法分隔区都必须触及重心所在的中心部分；这消除了“同一无根方案可从多个边界解释”的重复计数。

### Editorial

建圆方树：原顶点是圆点，每个点双是方点，方点连向该分量所有原顶点。以原圆点重心为根，`size[u]` 只统计子树中的圆点数。

固定 $s$。自底向上维护 `ways[u]`：子树内已封闭部分均能划成大小 $s$ 或 $s+1$ 的块，且唯一尚可向父亲连接的部分位于 $u$ 一侧。

- 在方点，分隔区要么继续连向子方向，要么该方向已完成划分。任一原点数小于 $s$ 的孩子子树都无法自成块，故当前状态为 0；其余孩子方案数相乘。
- 在圆点，所有 `size[child]<s` 的子树只能与当前圆点合并，形成 `tot`。大于 $s$ 的子树必须内部合法，方案数相乘。对恰好为 $s$ 的子树，可能整体封闭，也可能成为连通分隔区继续的唯一方向；只有当当前未封闭部分尚只含该圆点时，才出现这个选择计数。

$k=0$ 时只接受 `tot==s`。$k=1$ 时接受 `s<=tot<=s+1`；但若所有块实际都是 $s+1$，该方案也会在下一个 $s$ 里被统计，因此需减去“全部恰为 $s+1$”的 $k=0$ 计数。

最后不枚举 $s=1\ldots n/2$ 的全部值。令块数为 $t$，则 $s=\lfloor n/t\rfloor$；除法分块告诉我们这些商只有 $O(\sqrt n)$ 种。对 $k=0$，只有 $s\mid n$ 可行。

### 正确性与复杂度

圆方树定理保证合法 $E'$ 与连通方点分隔区一一对应；删去该区域后，每个圆点块恰含一个 $V'$ 顶点，相邻分隔方点所对应的原边集也被唯一确定。固定 $s$ 后，对根子树归纳：小于 $s$ 的部分不得封闭，大于等于 $s$ 的部分必须由孩子状态完成，圆/方两类转移因而既不漏也不重。根状态成功恰等价于全树完成划分。

圆方树建造 $O(n+m)$。每个候选 $s$ 扫树一次，候选数 $O(\sqrt n)$，总时间 $O((n+m)\sqrt n)$，空间 $O(n+m)$。

### 核心伪代码与附件

```text
T = block_cut_tree(G)
root T at an original-vertex centroid
candidate_sizes = distinct floor(n/t), plus divisor-related sizes
answer = 0
for s in candidate_sizes:
    for u in reverse rooted order:
        if u is a block node:
            ways[u] = product of feasible large-child states
            reject any child too small to form a component
        else:
            absorb every child subtree smaller than s into u
            combine feasible large children
            count the unique size-s child that may continue the separator
    add root count; for k=1 subtract the all-(s+1) duplicate
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P9167.cpp)

### 实现细节

- Tarjan 必须用边编号跳过父边，不要用“跳过父亲顶点”代替。
- 方点不计入 `subtree_size`；数组容量要留到 $n+m$。
- 递归深度最坏为 $O(n+m)$；在栈很小的评测环境应改显式栈。
- 附件已对 $n\le7$、边数最多约 10 的随机连通简单图，枚举全部非空 $E'$ 对拍。

## 实现指南

两题都应先写一个可检查的状态语义，再写转移。P8294 可在断点中打印小树的 `f[u,v]`，P9167 可打印每个候选 $s$ 的根计数。若样例错，先查“边界还没结算的量”，而不是先查取模或容器。

## 扩展与联系

- P8294 的“外来权值延后定价”与树分解中保留未封口路径是同一思想：状态只向上层暴露必要信息。
- P9167 不是一般的“圆方树模板题”；关键是先由块数 $=|V'|$ 推出每块恰一端点，否则圆方树没有可直接计数的语义。
- 若 P8294 允许一个节点有任意多孩子，当前常数边序分类会失效；需再对孩子集做序列 DP。

## 总结与自检

1. P8294 的 $f[u,v]$ 为什么不需知道外来权值的来源？
2. 为什么每个有序点对只应放在其 LCA 的桶中？
3. P9167 中“每个最终块恰含一个 $V'$ 顶点”的两个不等式分别来自哪里？
4. $k=1$ 时为什么要减去所有块均为 $s+1$ 的方案？

## 课后训练建议

1. 先读 P8294 Observations，自己列出一个叶子、一个单孩子节点的全部断边相对次序；20 分钟后看 Hint 2。
2. 读完 P8294 不必立即独立写 $O(n^2)$ 代码，但应能用 $n\le8$ 的全排列程序解释每个 DP 状态。
3. P9167 先对树图写边集暴力，再加一个三角形，观察圆方树为何必须出现。