题解 CF1060F 【Shrinking Tree】

· · 题解

一个比较难以理解的dp神题。

首先我们可以考虑每次随机缩一条边等效于有一个长度为n-1的边的操作序列，那么我们可以用序列计数的角度去处理这个东西，每个操作序列的边都有一半的概率选择一个端点，那对于我们钦定的一个点rt，在一个操作序列中它会有一定概率最后保留，那么我们可以求出所有操作序列这个点被保留的概率和，最后除个(n-1)!即可。

现在我们干脆把rt这个点提成根做一遍树形dp。但是这个dp如何入手呢？我们不妨假设（或者说叫钦定）一种状态就是考虑u这个点，rt现在已经克服重重困难来到了u点，但是rt怎么来的u点我们并不关心，我们仅关心u子树内的所有边的序列，因为我们可以使用诸如组合数之类的方式来合并两个操作序列。那么我们的大体思路应该是dp[u]为当rt这个编号转移到u点并将其取代之后，u这棵子树缩成一个rt编号的大点的操作序列的方案数（或者说是概率）。

我们考虑这个dp有没有什么值得转移的地方。我们知道u这个操作序列是它儿子的操作序列加上连向儿子的边混合而成的。那么我们不妨这样转移：

当合并过来一个儿子v的边的序列的时候，应该是这个儿子子树的边序列+这条连向儿子的边，所以，我们不妨在每个儿子处单独处理把这条父亲边插到自己的边序列中得到的边序列g，这样我们在父亲u处就考虑所有儿子g序列的合并就行了。

考虑(u,v)啥时候加入v的边序列，可以分两种情况：

①：rt已经移动至u，那么现在u就相当于rt，那么合并(u,v)这条边的时候必须有\frac 1 2的概率不让rt死掉，除此之外我们给(u,v)随便插个位置就好了。

②：rt还未移动至u，那么我合并(u,v)这条边最终编号是啥并没有关系，但是，我们现在的问题是必须保证给(u,v)插入一个位置的时候rt还没有移动至u。

那么现在我们就需要改一下dp状态了，我们设dp[u][i]为仅考虑u子树里的边序列，当rt移动到u的时候边序列还有最后i条没有合并的边序列的概率和。然后对于那个对儿子扩充的g序列我们设g[v][i]为仅考虑v子树和它父亲边的边序列，当rt移动到它的父亲u时这个序列还剩下最后i条没有合并的边序列的概率和。

这样的话，我们重新来看一下上面两个情况：

①：显然对于一个g[v][i]，(u,v)要插到末尾i个位置中去，那枚举(u,v)之后有多少条边，然后合并完(u,v)就相当于rt移动到了v上，就归纳到了v本身的边序列，所以g[v][i]=\frac 1 2\sum_{j=0}^{i-1}dp[v][j]。

②：对于g[v][i]这个序列来说我们只需把(u,v)插到前size[v]-i个已经合并的位置就行了，所以g[v][i]=(size[v]-i)dp[v][i]。

那么现在我们把每个儿子的g序列搞出来了，如何合并呢？其实，我们并不用考虑那么多，可以发现，儿子的边序列其实是互不影响的，因为在合并(u,v)的时候我们已经通过讨论避免了rt死掉，而每个儿子迟早会有一个点遇到rt，所以我们可以独立的合并儿子的g序列，只要我们保证在rt移动到u这个点的时刻（这是个最关键的时刻）之前已经合并了的边都在前面，之后没合并的边都在后面，就是这样：

那么我们考虑两个儿子x,y的合并，就是：

g[x][i]g[y][j]C_{size[x]-i+size[y]-j}^{size[x]-i}C_{i+j}^i\to dp[u][i+j]

前面的C是在这个时刻之前已经合并完的边序列混合起来，后面的C是在这个时刻之后的。

然后就O(n^4)了，还有要相信double，不太大的数据范围它还是能够处理阶乘组合数之类的……

上代码~

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
namespace ywy {
    double dp[55][55], g[55], jc[55];
    inline double cnm(int n, int m) {
        if (n < m)
            return (0);
        return ((jc[n] / jc[m]) / jc[n - m]);
    }
    typedef struct _b {
        int dest;
        int nxt;
    } bian;
    bian memchi[1000001];
    int gn = 1, heads[55];
    inline void add(int s, int t) {
        memchi[gn].dest = t;
        memchi[gn].nxt = heads[s];
        heads[s] = gn;
        gn++;
    }
    int size[55];
    double h[55];
    void dfs(int pt, int baba) {
        size[pt] = 1;
        dp[pt][0] = 1;
        for (register int i = heads[pt]; i; i = memchi[i].nxt) {
            if (memchi[i].dest == baba)
                continue;
            dfs(memchi[i].dest, pt);
            for (register int j = 0; j <= size[memchi[i].dest]; j++) {
                g[j] = 0;
                for (register int k = 0; k < j; k++) g[j] += 0.5 * dp[memchi[i].dest][k];
                g[j] += (size[memchi[i].dest] - j) * dp[memchi[i].dest][j];
            }
            for (register int j = 0; j <= size[pt] + size[memchi[i].dest]; j++) h[j] = 0;
            for (register int j = 0; j < size[pt]; j++) {
                for (register int k = 0; k <= size[memchi[i].dest]; k++) {
                    h[j + k] += dp[pt][j] * g[k] *
                                cnm(size[pt] - 1 - j + size[memchi[i].dest] - k, size[pt] - 1 - j) *
                                cnm(j + k, j);
                }
            }
            size[pt] += size[memchi[i].dest];
            for (register int j = 0; j < size[pt]; j++) dp[pt][j] = h[j];
        }
    }
    void ywymain() {
        int n;
        cin >> n;
        jc[0] = 1;
        for (register int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i;
        for (register int i = 1; i < n; i++) {
            int s, t;
            cin >> s >> t;
            add(s, t);
            add(t, s);
        }
        for (register int i = 1; i <= n; i++) {
            memset(dp, 0, sizeof(dp));
            dfs(i, 0);
            printf("%.10lf\n", dp[i][n - 1] / jc[n - 1]);
        }
    }
}
int main() {
    ywy::ywymain();
    return (0);
}