# 哈根农场题解

**并列方案：出题人的子树期望 DP；Codex（GPT-6）推导的逐边概率求和。** 两者均为 $O(n^2)$ 时间。逐边方法将运行空间从 $O(n^2)$ 降到 $O(n)$ ，因此选为 `std.cpp` ；子树 DP 能保留按选取数量分类的中间结果。以下分别给出思路、证明与适用范围，不以未测量的速度比较作为选择依据。

## 1. 最短闭合路线

连接所有苹果节点的最小子树是唯一的。任何闭合路线若需要经过一条边，就必须穿过它再返回，因此至少经过两次。沿最小子树做一次往返遍历即可达到这个下界。

所以答案是最小子树边长和的两倍。对单个苹果，边长和为零。以下用线性期望，把每条边的贡献相加。

## 2. 固定生成子树时，一条边被使用的概率

设边连接父节点与子节点 $v$ ，$v$ 的子树大小为 $t$ .它只有在生成根 $u$ 是 $v$ 的严格祖先时才可能被使用。记 $u$ 子树大小为 $s$ ，则这条边把生成范围分成 $t$ 与 $s-t$ 两部分。

在苹果数量固定为 $k$ 时，边不被使用当且仅当全部苹果落在同一侧。这两种事件在 $k\ge1$ 时互斥，因此使用概率为

$$1-\frac{\binom tk+\binom{s-t}k}{\binom sk}$$

规定选择数超出集合大小时组合数为零。现在还要对均匀的 $k=1,\ldots,s$ 求平均。对 $0\le t<s$ ，有

$$\sum_{k=1}^{s}\frac{\binom tk}{\binom sk}=\frac{t}{s-t+1}$$

证明：把 $k=0$ 项补上，使用

$$\frac{\binom tk}{\binom sk}=\frac{\binom{s-k}{s-t}}{\binom st}$$

再用组合数的逐项求和恒等式，和为 $(s+1)/(s-t+1)$ ，减去一即可。

因此对给定生成根，这条边的使用概率为

$$p(s,t)=1-\frac1s\left(\frac{t}{s-t+1}+\frac{s-t}{t+1}\right)$$

设边长为 $w_v$ ，最终答案为

$$E=\frac2n\sum_{v\ne1}w_v\sum_{u\text{ 为 }v\text{ 的严格祖先}}p(\mathrm{size}(u),\mathrm{size}(v))$$

## 3. 逐边实现与证明

先用显式遍历求父节点、边长和子树大小。预处理 $1,\ldots,n+1$ 的模逆元。对每个非根节点沿父指针枚举祖先，代入概率式，累加并乘边长、二和 $n$ 的逆元。

概率公式逐一涵盖“随机根、随机数量、均匀子集”三层随机性；最短闭合路线与边使用事件等价，线性期望不要求不同边独立。因此求和就是所求期望。

祖先与后代的有序对至多 $n(n-1)/2$ 个，时间为 $O(n^2)$ ，空间为 $O(n)$ .所有分母都在 $1$ 到 $n+1$ 内，小于质数 $P$ .零边权与 $n=1$ 无须额外调整。

## 4. 出题人解法：子树期望 DP

设 $s_v$ 是节点 $v$ 的子树大小，$D_v(k)$ 表示从该子树均匀选择 $k$ 个节点后，把这些节点全部连接到 $v$ 的边长和的期望。定义 $D_v(0)=0$ .这个状态允许强制走到 $v$ ，之后再扣除不需要到达 $v$ 的情况。

初始只有节点 $v$ ，大小为一，两个状态均为零。把大小为 $t$ 的子树 $c$ 合并到大小为 $s$ 的已处理部分时，若总共选择 $k$ 个节点，其中 $j$ 个来自 $c$ ，概率为

$$\frac{\binom tj\binom s{k-j}}{\binom{s+t}k}$$

这个分配下的期望边长为 $D_{\mathrm{old}}(k-j)+D_c(j)+w_c[j>0]$ .对所有合法 $j$ 加权求和即可转移。每个子树内部的选择在给定数量后仍均匀，所以转移正确。

求完所有 $D_v(k)$ 后，令

$$L_v(k)=\binom{s_v}kD_v(k)-\sum_{c\text{ 为 }v\text{ 的儿子}}\binom{s_c}k\bigl(D_c(k)+w_c\bigr)$$

其中只对 $k\le s_c$ 的项求和。$L_v(k)$ 是所有大小为 $k$ 、且所选节点最低公共祖先恰为 $v$ 的集合的最小连通子树长度总和。原因是全部所选节点若位于同一个儿子子树，强制连接到 $v$ 多走的边及其全部路径贡献都被扣除；其余集合的最小连通子树恰好经过 $v$ .

一个这样的集合可以由任意包含 $v$ 的祖先子树生成。沿根到 $v$ 的遍历路径维护

$$W_v(k)=\sum_{u\text{ 为 }v\text{ 的祖先或 }u=v}\frac1{s_u\binom{s_u}k}$$

仅累加 $k\le s_u$ 的项。进入或离开一个节点时，加上或减去它的贡献。最终

$$E=\frac2n\sum_v\sum_{k=1}^{s_v}L_v(k)W_v(k)$$

每个非空苹果集合有唯一最低公共祖先，因此不重不漏。预处理组合数及逆组合数；合并状态的非平凡配对可按两个节点在何次合并中首次相遇计数，总计 $O(n^2)$ ，其余状态扫描也至多 $O(n^2)$ .总时间与存储表空间均为 $O(n^2)$ .

若需要查询某个子树固定选择 $k$ 个节点时的路径期望，DP 的状态可继续使用。只求题目给定分布下的总期望时，逐边方法免去这些二维表。

## 数据与验证

`tests/generate.py` 覆盖链、星形、平衡树、扫帚形、零权边和随机树。小规模独立校验枚举生成根、苹果数量及全部子集，直接统计连接苹果的边。参考时限见[评测环境与性能](../../../docs/评测环境与性能.md)。