perspective的博客

博客

题解

2021-12-08 13:47:43 By perspective

在解决问题之前首先要明确 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 的期望值了。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。