GitHub 源文件 Markdown English

哈根农场题解

并列方案：出题人的子树期望 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 覆盖链、星形、平衡树、扫帚形、零权边和随机树。小规模独立校验枚举生成根、苹果数量及全部子集，直接统计连接苹果的边。参考时限见评测环境与性能。