TopCoder SRM 561 Orienteering 题解

作者：钟知闲
关键字：图论 数学 概率与期望
题目简述

以网格图的形式给出一个无根树，以及树的点集的一个子集 $C$。现从 $C$ 的所有大小为 $K$ 的子集中等概率选取一个子集 $S$，记 $\mathrm{length}$ 为树中经过所有 $S$ 中的点的最短路径长度（路径长度定义为经过的边数，可以重复经过同一条边，此时长度需要被计算多次）。给定无根树、点集 $C$ 以及整数 $K$，求 $\mathrm{length}$ 的期望值。
树的节点数不超过 $50\times 50$，$|C|\le 300$，$2\le K\le |C|$。
题解

在解决问题之前首先要明确 $\mathrm{length}$ 如何计算，即对于给定的点集 $S$，经过 $S$ 中所有点的最短路径长度应该怎么求。
由于本题给出的网格图是一个树，所以可以利用树的性质来解决问题。例如，树上任意两点 $u,v$ 间简单路径唯一，且该路径为 $u,v$ 间最短路径；树的每一条边都是割边，删除后导致 $u,v$ 不连通当且仅当该边在 $u$ 到 $v$ 的简单路径上，等等。
类比树上任意两点之间连通，可以得到一个基本的性质：
性质1 对于任意 $S\subseteq C$ 和 $a,b\in S$，存在一条从 $a$ 出发经过 $S$ 中所有点到达 $b$ 的路径。
证明 设 $S={v0,v_1,...,v{|S|-1}}$，其中 $v0=a$，$v{|S|-1}=b$，构造路径 $P$，先从 $v0$ 到 $v_1$，从 $v_1$ 到 $v_2$，…，最后从 $v{|S|-2}$ 到 $v{|S|-1}$。因为 $\forall i\in (1,|S|]$，$v{i-1}$ 和 $v_i$ 在树上连通，所以这样构造的路径 $P$ 一定是合法的。
设 $P$ 是经过 $S$ 中所有点的最短路径，将 $S$ 中的点按照第一次被 $P$ 经过的时间排序，记为 $v0,v_1,...,v{|S|-1}$，那么有：
性质2 $P$ 以 $v0$ 为起点，$v{|S|-1}$ 为终点。
证明 假如 $P$ 不以 $v_0$ 为起点，那么从 $P$ 的起点到 $v_0$ 这一段路径没有经过 $S$ 中的点，去掉后 $P$ 更短，与 $P$ 是最短路径矛盾。
类似地，如果 $P$ 不以 $v{|S|-1}$ 为终点，则 $v{|S|-1}$ 之后的路径可以去掉。
性质3 $\forall i\in[1,|S|)$，$P$ 中第一次经过 $v{i-1}$ 之后必沿着 $v{i-1}$ 到 $v_i$ 的简单路径到达 $v_i$。
证明 如果 $P$ 中从第一次经过 $v_{i-1}$ 到第一次经过 $v_i$ 这一段不是简单路径，那么改成简单路径后 $P$ 更短，与 $P$ 是最短路径矛盾。
性质4 边 $e\in P$ 当且仅当删除 $e$ 后 $S$ 中存在两点不连通（即 $\exists u,v\in S$，$e$ 在 $u$ 到 $v$ 的简单路径上）。
证明 设删除 $e$ 后存在 $u',v'\in S$ 不连通，那么删除 $e$ 后不可能有 $u',v'\in P$，因此要使 $u',v'\in P$ 必有 $e\in P$。
如果删除 $e$ 后任意 $u',v'\in S$ 仍连通，说明 $\forall u',v'\in S$，$e$ 不在 $u'$ 到 $v'$ 的唯一简单路径上，因此 $e\not\in P$。
性质5 任意边 $e$ 在 $P$ 中经过最多 $2$ 次。
证明 假设 $e=(u,v)$ 在 $P$ 中出现了 $3$ 次或以上，第 $1$ 次为 $u\rightarrow v$，第 $2$ 次为 $v\rightarrow u$，第 $3$ 次为 $u\rightarrow v$，记 $P'$ 为第 $1$ 次经过 $e$ 后到第 $2$ 次经过 $e$ 前这一段从 $v$ 到 $v$ 的路径，那么可以把第 $1$ 次经过 $e$ 前到第 $2$ 次经过 $e$ 后的路径（$u\rightarrow v$，$P'$，$v\rightarrow u$）删掉，在第 $3$ 次经过 $e$ 后加上 $P'$ 这一段，这样 $P$ 经过的点集不变但长度减少了 $2$，与 $P$ 是最短路径矛盾。
性质6 边 $e$ 在 $P$ 中经过恰 $1$ 次当且仅当 $v0$ 到 $v{|S|-1}$ 的简单路径包含 $e$。
证明 若 $v0$ 到 $v{|S|-1}$ 的简单路径包含 $e$，那么删去 $e$ 后 $v0$ 与 $v{|S|-1}$ 不连通，故必有 $e\in P$。并且 $e$ 不会在 $P$ 中出现两次，否则若 $e=(u,v)$，第一次为 $u\rightarrow v$，第二次为 $v\rightarrow u$，因之后不再经过 $e$，故删掉 $e$ 后 $v0$ 和 $v{|S|-1}$ 均与 $u$ 在同一连通块，矛盾。
反过来，若边 $e=(u,v)$ 在 $P$ 中经过恰 $1$ 次，那么删去 $e$ 后，$v0$ 与 $u$ 在同一连通块，$v{|S|-1}$ 与 $v$ 在同一连通块，而 $u,v$ 不连通，从而 $e$ 在 $v0$ 到 $v{|S|-1}$ 的简单路径上。
根据以上性质，可以得到，对于点集 $S$，若经过 $S$ 中所有点的最短路径 $P$ 起点为 $u$，终点为 $v$，那么
length(P)=2|ES?path(u,v)|+|path(u,v)|\=2|ES|?|path(u,v)|
length(P)=2|ES?path(u,v)|+|path(u,v)|\=2|ES|?|path(u,v)|

其中，$\mathrm{length}(P)$ 为路径 $P$ 的长度，$E_S$ 为删除后会导致 $S$ 中存在两点不连通的边集，即出现在某两点 $u,v\in S$ 之间的简单路径上的所有边的集合，$\mathrm{path}(u,v)$ 为 $u,v$ 之间的简单路径的边集，显然 $\mathrm{path}(u,v)\subseteq E_S$。
显然要使 $\mathrm{length}(P)$ 最短，就要选择 $u,v$ 使得 $|\mathrm{path}(u,v)|$ 最大，即 $u,v$ 是 $S$ 中的最远点对。设 $a,b$ 是 $S$ 中的最远点对，由性质1，必定存在从 $a$ 到 $b$ 的合法路径，也就存在从 $a$ 到 $b$ 的最短路径，即满足 (???)(???) 的路径。
从而，设 $D_S$ 为 $S$ 中最远点对（所有 $u,v\in S$ 中，$|\mathrm{path}(u,v)|$ 的最大值）的距离，则
length=2|ES|?DS
length=2|ES|?DS

现在我们考虑如何求 (???)(???) 的期望值，即 $E(\mathrm{length})$。由期望值的性质不难得出
E(length)=2E(|ES|)?E(DS)
E(length)=2E(|ES|)?E(DS)

因此只需分开计算 $|E_S|$ 和 $D_S$ 的期望值。
首先考虑如何计算 $|ES|$。用 $E$ 表示树的边集，显然 $E_S\subseteq E$。$E$ 的子集很多，不能枚举每个子集计算其概率。不过不难发现 $E(E_S)=\sum{e\in E}P(e\in E_S)$，即 $|E_S|$ 的期望就是每条边出现在 $E_S$ 内的概率之和，可以从这个角度进行思考。
对于 $e\in E$，$e\not\in E_S$ 当且仅当删去 $e$ 之后，$S$ 中的点全在同一个连通块内。设 $e$ 删去后的两个连通块 $A,B$（这里的连通块指的是点集）内属于 $C$ 的点数分别为 $s$ 和 $|C|-s$，由于 $C$ 的大小为 $K$ 的子集 $S$ 有 ${|C|\choose K}$ 个，满足 $S\subseteq A$ 的 $S$ 有 ${s\choose K}$ 个，满足 $S\subseteq B$ 的 $S$ 有 ${|C|-s\choose K}$ 个，且由于 $|S|=K\ge 2>|A\cap B|=0$，所以 $S\subseteq A$ 和 $S\subseteq B$ 互斥，故 $e\not\in E_S$ 的概率 P(e?ES)=(sK)(|C|K)+(|C|?sK)(|C|K)P(e?ES)=(sK)(|C|K)+(|C|?sK)(|C|K)
因此 P(e∈ES)=1?(sK)(|C|K)?(|C|?sK)(|C|K)P(e∈ES)=1?(sK)(|C|K)?(|C|?sK)(|C|K)
注意组合数的值可能很大，因此程序中直接计算可能溢出，超过浮点数的范围。记 $f(a,b,K)=\frac{a\choose K}{a+b\choose K}$，化简可得 f(a,b,K)=a!K!(a?K)!(a+b)!K!(a+b?K)!=a!(a?K)!?(a+b?K)!(a+b)!=a(a?1)…(a?K+1)(a+b)(a+b?1)…(a+b?K+1)f(a,b,K)=a!K!(a?K)!(a+b)!K!(a+b?K)!=a!(a?K)!?(a+b?K)!(a+b)!=a(a?1)…(a?K+1)(a+b)(a+b?1)…(a+b?K+1)
计算 $f(a,b,K)$ 的方法如下：
f(a, b, K):
x = 1
for i = 0 to K - 1:
x = x * (a - i) / (a + b - i)
return x
这样，根据期望的性质就能得出 E(|ES|)=∑e∈EP(e∈ES)=∑e∈E(1?f(se,|C|?se,K)?f(|C|?se,se,K))E(|ES|)=∑e∈EP(e∈ES)=∑e∈E(1?f(se,|C|?se,K)?f(|C|?se,se,K))
其中 $se$ 为删去 $e$ 之后其中一个连通块中属于 $C$ 的点数。这可以使用树形动态规划来求解：将无根树转成有根树，然后记 $s(v)$ 为以 $v$ 为根的子树中属于 $C$ 的节点个数，$c(v)$ 为 $v$ 的子节点集合。则可以计算所有的 $s(v)$：

$$\begin{equation} s(v)=\sum{v'\in c(v)}s(v')+[v\in C] \label{TreeDP} \end{equation}$$
若 $e=(u,v)$，则 $u,v$ 必有一个是另一个的父节点，不妨设 $u$ 是 $v$ 的父节点，那么 $s_e=s(v)$。
这样就能在 $O(|V|)$ 的时间内求出所有的 $s_e$，进而在 $O(|E|K)=O(|V|K)$ 的时间内求出 $E(|E_S|)$，其中 $V$ 为树的点集， $|V|=|E|+1$。由于 $|V|\le 50\times 50=2500$， $K\le 300$，这一步运行是比较快的。
接着再考虑如何计算 $E(D_S)$。因为 $C$ 中的点对只有 $|C|^2\le 300^2$ 个，所以可以枚举点对 $u,v\in C$，计算 $u,v$ 是 $S$ 的最远点对的概率。当然最远点对不唯一，为了使其唯一，我们重新定义一个点对 $u,v$ 的距离 d(u,v)=|path(u,v)|+2?h(u)+2?h(v)d(u,v)=|path(u,v)|+2?h(u)+2?h(v)
这里 $h(v)$ 是对每个点 $v$ 分配的编号，要求所有点的 $h(v)$ 是两两不同的正整数，这样 $d(u_1,v_1)=d(u_2,v_2)$ 要求两者的小数部分相同，即 $2^{-h(u_1)}+2^{-h(v_1)}=2^{-h(u_2)}+2^{-h(v_2)}$，考虑两者的二进制表示可知仅当 ${u_1,v_1}={u_2,v_2}$ 时等式成立。于是不同的点对距离不同，最远点对就唯一了。
现在考虑计算 $a,b$ 是 $S$ 的最远点对（所有 $a,b\in S$ 中， $d(a,b)$ 的最大值）的概率，那么需要满足的条件有
?v∈S?a,b,maxd(v,a),d(v,b)