大家好，Southeastern Championship 就要开始了，有很多同学好奇，在这样一场高难度的比赛中，如何夺冠呢？

其实非常简单，你只需要和 HY 组队，然后等 HY 把所有题都秒了，自然就夺冠了。是不是很简单？

有任何问题的同学可以在下面留言哦。

在解决问题之前首先要明确 length 如何计算，即对于给定的点集 $S$，经过 $S$ 中所有点的最短路径长度应该怎么求。

性质 1 对于任意 $𝑆 ⊆ 𝐶$ 和 $𝑎, 𝑏 ∈ 𝑆$，存在一条从 $𝑎$ 出发经过 $𝑆$ 中所有点到达 $𝑏$ 的路径。

证明 设 $𝑆 = {𝑣_0, 𝑣_1, \cdots, 𝑣_{|𝑆|−1}}$，其中 $𝑣_0 = 𝑎，𝑣_{|𝑆|−1} = 𝑏$，构造路径 $𝑃$，先从 $𝑣_0$ 到 $𝑣_1$，从 $𝑣_1$ 到 $𝑣_2$，…，最后从 $𝑣_{|𝑆|−2}$ 到 $𝑣_{|𝑆|−1}$。因为 $∀𝑖 ∈ (1, |𝑆|]$，$𝑣_{𝑖−1}$ 和 $𝑣_𝑖$ 在树上连通，所以这样构造的路径 $𝑃$ 一定是合法的。

设 $𝑃$ 是经过 $𝑆$ 中所有点的最短路径，将 $𝑆$ 中的点按照第一次被 $𝑃4 经过的时间排序，记为$𝑣_0, 𝑣_1, \cdots, 𝑣_{|𝑆|−1}$，那么有：

性质 2 $𝑃$ 以 $𝑣_0$ 为起点，$𝑣_{|𝑆|−1}$ 为终点。

证明 假如 $𝑃$ 不以 $𝑣_0$ 为起点，那么从 $𝑃$ 的起点到 $𝑣_0$ 这一段路径没有经过 $𝑆$ 中的点，去掉后 $𝑃$ 更短，与 $𝑃$ 是最短路径矛盾。类似地，如果 $𝑃$ 不以 $𝑣_{|𝑆|−1}$ 为终点，则 $𝑣_{|𝑆|−1}$ 之后的路径可以去掉。

性质 3 $∀𝑖 ∈ [1, |𝑆|)$，$𝑃$ 中第一次经过 $𝑣_{𝑖−1}$ 之后必沿着 $𝑣_{𝑖−1}$ 到 $𝑣_𝑖$ 的简单路径到达 $𝑣_𝑖$。

证明 如果 $𝑃$ 中从第一次经过 $v_{𝑖−1}$ 到第一次经过 $𝑣_𝑖$ 这一段不是简单路径，那么改成简单路径后 $𝑃$ 更短，与 $𝑃$ 是最短路径矛盾。

性质 4 边 $𝑒 ∈ 𝑃$ 当且仅当删除 $𝑒$ 后 $𝑆$ 中存在两点不连通（即 $∃𝑢, 𝑣 ∈ 𝑆$，$𝑒$ 在 $𝑢$ 到 $𝑣$ 的简单路径上）。

证明 设删除 $𝑒$ 后存在 $𝑢′, 𝑣′ ∈ 𝑆$ 不连通，那么删除 $𝑒$ 后不可能有 $𝑢′, 𝑣′ ∈ 𝑃$，因此要使 $𝑢′, 𝑣′ ∈ 𝑃$ 必有 $𝑒 ∈ 𝑃$。如果删除 $𝑒$ 后任意 $𝑢′, 𝑣′ ∈ 𝑆$ 仍连通，说明 $∀𝑢′, 𝑣′ ∈ 𝑆$，$𝑒$ 不在 $𝑢′$ 到 $𝑣′$ 的唯一简单路径上，因此 $𝑒 ∉ 𝑃$。

性质 5 任意边 $𝑒$ 在 $𝑃$ 中经过最多 $2$ 次。

证明 假设 $𝑒 = (𝑢, 𝑣)$ 在 $𝑃$ 中出现了 $3$ 次或以上，第 $1$ 次为 $𝑢 → 𝑣$，第 $2$ 次为 $𝑣 → 𝑢$，第 $3$ 次为 $𝑢 → 𝑣$，记 $𝑃′$ 为第 $1$ 次经过 $𝑒$ 后到第 $2$ 次经过 $𝑒$ 前这一段从 $𝑣$ 到 $𝑣$ 的路径，那么可以把第 $1$ 次经过 $𝑒$ 前到第 $2$ 次经过 $𝑒$ 后的路径（$𝑢 → 𝑣$，$𝑃′$，$𝑣 → 𝑢$）删掉，在第 $3$ 次经过 $𝑒$ 后加上 $𝑃′$ 这一段，这样 $𝑃$ 经过的点集不变但长度减少了 $2$，与 $𝑃$ 是最短路径矛盾。

性质 6 边 $𝑒$ 在 $𝑃$ 中经过恰 $1$ 次当且仅当 $𝑣_0$ 到 $𝑣_{|𝑆|−1}$ 的简单路径包含 $𝑒$。

证明 若 $𝑣_0$ 到 $𝑣_{|𝑆|−1}$ 的简单路径包含 $𝑒$，那么删去 $𝑒$ 后 $𝑣_0$ 与 $𝑣_{|𝑆|−1}$ 不连通，故必有 $𝑒 ∈ 𝑃$。并且 $𝑒$ 不会在 $𝑃$ 中出现两次，否则若 $𝑒 = (𝑢, 𝑣)$，第一次为 $𝑢 → 𝑣$，第二次为 $𝑣 → 𝑢$，因 之后不再经过 $𝑒$，故删掉 $𝑒$ 后 $𝑣_0$ 和 $𝑣_{|𝑆|−1}$ 均与 $𝑢$ 在同一连通块，矛盾。反过来，若边 $𝑒 = (𝑢, 𝑣)$ 在 $𝑃$ 中经过恰 $1$ 次，那么删去 $𝑒$ 后，$𝑣_0$ 与 $𝑢$ 在同一连通块，$𝑣_{|𝑆|−1}$ 与 $𝑣$ 在同一连通块，而 $𝑢, 𝑣$ 不连通，从而 $𝑒$ 在 $𝑣_0$ 到 $𝑣_{|𝑆|−1}$ 的简单路径上。

根据以上性质，可以得到，对于点集 $𝑆$，若经过 $𝑆$ 中所有点的最短路径 $𝑃$ 起点为 $𝑢$，终点为 $𝑣$，那么:

$$length(𝑃) = 2|𝐸_𝑆 − path(𝑢, 𝑣)| + |path(𝑢, 𝑣)| = 2|𝐸_𝑆| − |path(𝑢, 𝑣)|$$

其中，$length(𝑃)$ 为路径 $𝑃$ 的长度，$𝐸_𝑆$ 为删除后会导致 $𝑆$ 中存在两点不连通的边集，即出现在某两点 $𝑢, 𝑣 ∈ 𝑆$ 之间的简单路径上的所有边的集合，$path(𝑢, 𝑣)$ 为 $𝑢, 𝑣$ 之间的简单路径的边集，显然 $path(𝑢, 𝑣) ⊆ 𝐸_𝑆$。

显然要使 $length(𝑃 )$ 最短，就要选择 $𝑢, 𝑣$ 使得 $|path(𝑢, 𝑣)|$ 最大，即 $𝑢, 𝑣$ 是 $𝑆$ 中的最远点对。设 $𝑎, 𝑏$ 是 $𝑆$ 中的最远点对，由性质 1，必定存在从 $𝑎$ 到 $𝑏$ 的合法路径，也就存在从 $𝑎$ 到 $𝑏$ 的最短路径，即满足 $\eqref{Length}$ 的路径。

从而，设 $𝐷_𝑆$ 为 $𝑆$ 中最远点对（所有 $𝑢, 𝑣 ∈ 𝑆$ 中，$|path(𝑢, 𝑣)|$ 的最大值）的距离，则 $length = 2|𝐸_𝑆| − 𝐷_𝑆$ 现在我们考虑如何求 $\eqref{Answer}$ 的期望值，即 $𝐸(length)$。由期望值的性质不难得出

$$𝐸(length) = 2𝐸(|𝐸_𝑆|) − 𝐸(𝐷_𝑆)$$

因此只需分开计算 $|𝐸_𝑆|$ 和 $𝐷_𝑆$ 的期望值。

首先考虑如何计算 $|𝐸_𝑆|$。用 $𝐸$ 表示树的边集，显然 $𝐸_𝑆 ⊆ 𝐸$。$𝐸$ 的子集很多，不能枚举每个子集计算其概率。不过不难发现 $𝐸(𝐸_𝑆) = \sum_{𝑒∈𝐸} 𝑃 (𝑒 ∈ 𝐸_𝑆)$，即 $|𝐸_𝑆|$ 的期望就是每条边出现在 $𝐸_𝑆$ 内的概率之和，可以从这个角度进行思考。

对于 $𝑒 ∈ 𝐸$，$𝑒 ∉ 𝐸_𝑆$ 当且仅当删去 $𝑒$ 之后，$𝑆$ 中的点全在同一个连通块内。设 $𝑒$ 删去后的两个连通块 $𝐴, 𝐵$（这里的连通块指的是点集）内属于 $𝐶$ 的点数分别为 $𝑠$ 和 $|𝐶| − 𝑠$，由于 $𝐶$ 的大小为 $𝐾$ 的子集 $𝑆$ 有 $\binom{|C|}{K}$ 个，满足 $𝑆 ⊆ 𝐴$ 的 $𝑆$ 有 $\binom sK$ 个，满足 $𝑆 ⊆ 𝐵$ 的 $𝑆$ 有 $\binom{|𝐶|−𝑠}{𝐾}$ 个，且由于 $|𝑆| = 𝐾 ≥ 2 > |𝐴 ∩ 𝐵| = 0$，所以 $𝑆 ⊆ 𝐴$ 和 $𝑆 ⊆ 𝐵$ 互斥，故 $𝑒 ∉ 𝐸_𝑆$ 的概率 $𝑃(𝑒 ∉ 𝐸_𝑆) = \frac{\binom{s}{K}}{\binom{C}{K}} + \frac{\binom{|C|-s}{K}}{\binom{|C|}{K}}$

因此 $𝑃 (𝑒 ∈ 𝐸𝑆) = 1 - \frac{\binom sK}{\binom{|C|}{K}} - \frac{\binom{|C|-s}{K}}{\binom{|C|}{K}}$

这样，根据期望的性质就能得出 $𝐸(|𝐸_𝑆|) = \sum_{𝑒∈𝐸} 𝑃(𝑒 ∈ 𝐸_𝑆)= \sum_{𝑒∈𝐸}(1 − 𝑓(𝑠_𝑒, |𝐶| − 𝑠_𝑒, 𝐾) − 𝑓(|𝐶| − 𝑠_𝑒, 𝑠_𝑒, 𝐾))$

其中 $𝑠_𝑒$ 为删去 $𝑒$ 之后其中一个连通块中属于 $𝐶$ 的点数。这可以使用树形动态规划来求解：将无根树转成有根树，然后记 $𝑠(𝑣)$ 为以 $𝑣$ 为根的子树中属于 $𝐶$ 的节点个数，$𝑐(𝑣)$ 为 $𝑣$ 的子节点集合。则可以计算所有的 $𝑠(𝑣)$：$𝑠(𝑣) = \sum_{𝑣′\in 𝑐(𝑣)}𝑠(𝑣′) +[𝑣\in 𝐶]$

若 $𝑒 = (𝑢, 𝑣)$，则 $𝑢, 𝑣$ 必有一个是另一个的父节点，不妨设 $𝑢$ 是 $𝑣$ 的父节点，那么 $𝑠_𝑒 = 𝑠(𝑣)$。这样就能在 $𝑂(|𝑉|)$ 的时间内求出所有的 $𝑠_𝑒$，进而在 $𝑂(|𝐸|𝐾) = 𝑂(|𝑉|𝐾)$ 的时间内求出 $𝐸(|𝐸_𝑆|)$，其中 $𝑉$ 为树的点集，$|𝑉 | = |𝐸| + 1$。由于 $|𝑉 | ≤ 50 × 50 = 2500$，$𝐾 ≤ 300$，这一步运行是比较快的。

接着再考虑如何计算 $𝐸(𝐷_𝑆)$。因为 $𝐶$ 中的点对只有 $|C|^2 ≤ 300^2$ 个，所以可以枚举点对 $𝑢, 𝑣 ∈ 𝐶$，计算 $𝑢, 𝑣$ 是 $𝑆$ 的最远点对的概率。当然最远点对不唯一，为了使其唯一，我们重新定义一个点对 $𝑢, 𝑣$ 的距离 $𝑑(𝑢, 𝑣) = |path(𝑢, 𝑣)| + 2^{−ℎ(𝑢)} + 2^{−ℎ(𝑣)}$ 这里 $ℎ(𝑣)$ 是对每个点 $𝑣$ 分配的编号，要求所有点的 $ℎ(𝑣)$ 是两两不同的正整数，这样 $𝑑(𝑢_1, 𝑣_1) = 𝑑(𝑢_2, 𝑣_2)$ 要求两者的小数部分相同，即 $2^{−ℎ(𝑢_1)} + 2^{−ℎ(𝑣_1)} = 2^{−ℎ(𝑢_2)} + 2^{−ℎ(𝑣_2)}$，考虑两者的二进制表示可知仅当 $\{𝑢_1, 𝑣_1\} = \{𝑢_2, 𝑣_2\}$ 时等式成立。于是不同的点对距离不同，最远点对就唯一了。

现在考虑计算 $𝑎, 𝑏$ 是 $𝑆$ 的最远点对（所有 $𝑎, 𝑏 ∈ 𝑆$ 中，$𝑑(𝑎, 𝑏)$ 的最大值）的概率，那么需要满足的条件有

1. $∀𝑣 ∈ 𝑆 − {𝑎, 𝑏}, max{𝑑(𝑣, 𝑎), 𝑑(𝑣, 𝑏)} < 𝑑(𝑎, 𝑏)$
2. $∀𝑢, 𝑣 ∈ 𝑆 − {𝑎, 𝑏}, 𝑑(𝑢, 𝑣) < 𝑑(𝑎, 𝑏)$

事实上只要满足条件 $\eqref{Cond1}$ 就够了。为什么呢？

假设现在条件 $\eqref{Cond1}$ 已经满足了，那么对任意 $𝑢, 𝑣 ∈ 𝑆 − \{𝑎, 𝑏\}$，设 $𝐷$ 为 $𝑎$ 和 $𝑏$间简单路径，$𝑢′, 𝑣′$ 为 $𝐷$ 上的两点，满足 $𝑢$ 到 $𝑢′$ 的简单路径与 $𝐷$ 不相交，$𝑣$ 到 $𝑣′$ 的简单路径与 $𝐷$ 不相交（删除后每个连通块恰有一个点属于 $𝐷$，因为 $𝐷$ 中的点数比 $𝐷$ 中的边数多 $1$，且 $𝐷$ 中的任意两点不可达），且 $𝐷$ 上从 $𝑎$ 到 $𝑏$ 先经过 $𝑢′$ 再经过 $𝑣′$，即 $path(𝑎, 𝑢′) ∪ path(𝑢′, 𝑣′) ∪ path(𝑣′, 𝑏) = path(𝑎, 𝑏)$

（否则交换 $𝑢$ 和 $𝑣$、$𝑢′$ 和 $𝑣′$）根据 $\eqref{Cond1}$，有 $|path(𝑢, 𝑢′)|+|path(𝑢′, 𝑏)|+2^{−ℎ(𝑢)}+2^{−ℎ(𝑏)} < |path(𝑎, 𝑢′)| + |path(𝑢′, 𝑏)| + 2^{−ℎ(𝑎)} + 2^{−ℎ(𝑏)}$ 即 $|path(𝑢, 𝑢′)| + 2^{−ℎ(𝑢)} < |path(𝑎, 𝑢′)| + 2^{−ℎ(𝑎)}$ 同理 $|path(𝑣, 𝑣′)| + 2^{−ℎ(𝑣)} < |path(𝑏, 𝑣′)| + 2^{−ℎ(𝑏)}$ 所以 $𝑑(𝑢, 𝑣) = |path(𝑢, 𝑢′)| + |path(𝑢′, 𝑣′)| + |path(𝑣′, 𝑣)| + 2^{−ℎ(𝑢)} + 2^{−ℎ(𝑣)} < |path(𝑎, 𝑢′)| + |path(𝑢′, 𝑣′)| + |path(𝑏, 𝑣′)|+ 2^{−ℎ(𝑎)} + 2^{−ℎ(𝑏)} = 𝑑(𝑎, 𝑏)$

因此我们证明了满足 $\eqref{Cond1}$ 的同时必然满足 $\eqref{Cond2}$。这样问题就简单很多了：对于每对 $𝑎, 𝑏 ∈ 𝐶$，统计满足 $\eqref{Cond1}$ 的 $𝑆$ 的个数。在此之前，我们先进行预处理：对每个 $𝑣 ∈ 𝐶$，从 $𝑣$ 出发做一遍广度优先搜索，就能得到 $𝑣$ 到每个点的距离。这样的预处理复杂度是 $𝑂(|𝐶||𝑉 |)$ 的，没有时间上的问题。预处理之后就可以找出 $𝐶 − \{𝑎, 𝑏\}$ 中所有满足条件的点的集合 $𝐹$，即 $𝐹 = {𝑣 ∈ 𝐶 − \{𝑎, 𝑏\}| \max{𝑑(𝑣, 𝑎), 𝑑(𝑣, 𝑏)} < 𝑑(𝑎, 𝑏)}$

现在考虑概率怎么算。首先 $𝐶$ 一共有 $\binom{|𝐶|}{𝐾}$ 个大小为 $𝐾$ 的子集，满足 $𝑎, 𝑏 ∈ 𝑆$ 且 $𝑆 − \{𝑎, 𝑏\} ⊆ 𝐹$ 的子集 $𝑆$ 有 $\binom{|𝐹|}{𝐾−2}$ 个（这是由于去掉确定的 $𝑎, 𝑏$ 以外，要从 $𝐹$ 中取 $𝐾 − 2$ 个点作为 $𝑆 − \{𝑎, 𝑏\}$ ），因此 $𝑆$ 满足 $\eqref{Cond1}$ 的概率为 $\frac{\binom{|F|}{K-2}}{\binom{|C|}{K}}$

这样，枚举点对 $𝑎, 𝑏 ∈ 𝐶$，再通过枚举得到 $|𝐹|$，计算 $\eqref{Value}$ 的值乘 $𝑎, 𝑏$ 的距离，所有乘积的和就是 $𝐸(𝐷_𝑆)$。时间复杂度为 $𝑂(|𝐶|^3)$，因为 $|𝐶| ≤ 300$，所以可以通过。

最后，把 $𝐸(|𝐸_𝑆|)$ 和 $𝐸(𝐷_𝑆)$ 代入 $\eqref{ExpectedValue}$ 就能求出 length 的期望值了。