Centaur Company

作者：吕欣

关键字：树上DP，背包，概率与期望

题意简述

有一个 $n$ 个节点的树，有两人分这棵树的节点，每个节点会等概率地分到某一方；现在两人希望连接若干条边，使得他自己的节点可以不经过对方节点地互相连通。每个节点可以免费连一条边，除此之外，每个点的每一条额外的连边会产生 $1$ 点费用。双方总会选择使费用最小的连边方式，求连边总费用的期望。

约定：$n\leq36$

分析

首先双方的情况是对称的，我们只需要算出其中一方的期望，再乘 $2$ 即可；

我们考虑怎样的连边方式是最优的，设某一方分到了 $x$ 个节点，这 $x$ 个节点已经构成了 $y$ 个连通块，显然只需要连接 $y-1$ 条边，每个节点的第一条连边不需要支付费用，不难得到一个连边的费用下界 $max(2y-x-2,0)$；我们下面证明，这个下界是可以达到的：

1. 先奠基，$1$ 个连通块的情况下，费用显然为 $0$，$1<x=y$的情况下，把它们连成一条链，费用为 $x-2$
2. 考虑有 $x$ 个点，$y$ 个连通块的情况，其中 $2\leq y<x$，则我们能找到一个连通块中有多于一个点，我们取其中某个点和其他连通块的某个点相连，可以得到一个 $x-2$ 个点，$y-1$ 个连通块的子问题，它的费用下界为 $max(2y-x-2,0)$;
3. 由归纳法，知命题对所有 $(x,y)$ 成立

所以我们可以得到一个很显然有用的结论：把 $x$ 个点，$y$ 个连通块连起来需要支付 $max(2y-x-2,0)$ 的费用。

算法一

由分析，不难发现，我们只关注有多少个点、形成了多少连通块，而不必关注连通块的具体形态
另一方面，节点的不同分配方案数 $2^n$ 在 long long 范围之内，我们考虑统计出所有不同的 $(x,y)$ 的方案数，统一计算对答案的贡献，除以 $2^n$ 即可

不难设计出一个DP方程 $f[i][x][y][0/1]$，表示考虑某一方，它在 $i$ 为根的子树中得到了 $x$ 个点，连成了 $y$ 个连通块，同时有/没有选择 $i$ 的父亲的方案数。

转移的话，我们需要做一个树上的二维背包，同时注意讨论新的连通块的形成

时间复杂度 $O(n^5)$，空间复杂度 $O(n^3)$

算法二

考虑费用的计算公式 $2y-x-2$，这是一个关于 $x$ 和 $y$ 的一次函数，并且 $x$、$y$ 的系数都比较小，因为我们实际关心的是 $2y-x$ 的值，这启发我们可以优化算法一中的DP方程，把 $x$、$y$ 两维合并成一维。

我们设 $f[i][a][0/1]$ 表示以 $i$ 为根的子树中，选的点满足 $2y-x=a$，$i$ 的父亲有/没有被选的方案数。

为了实现方便，可以使用记忆化搜索，转移的时候枚举根节点选或不选，考虑连通块数量的变化情况，跑背包即可。

时间复杂度：不难分析出一个 $O(n^3)$ 的上界，足以通过本题。在此基础上，对某个子树来说，它的背包的大小关于子树大小是成线形关系的，根据树上背包按 $size$ 合并的那一套理论，稍加优化，能得到一个 $O(n^2)$ 的算法。

空间复杂度：$O(n^2)$