题解 AT690 【木】

· · 题解

Description

给定一棵大小为 n 的树，用另外 n 个点加边构造出这棵树，要求构造时所被边连到的点联通，求有多少连边顺序。

### Solution ![](https://i.loli.net/2020/02/01/dOch6MFrGLkZyEo.png) 连边大致有从上向下和从下向上两个顺序。由于是无根树，可以枚举一个点作为根节点，让所有的边只能从根节点开始往下连，即为从根节点开始生长到叶子节点。 设 $f_x$ 为 $x$ 子树的方案数，$sz_x$ 为子树 $x$ 有多少条边。 初始令 $f_x = 1$。假设处理到了 $x$ 的儿子 $y$，根据乘法原理，$f_x = f_x \times f_y$。但是儿子子树的加边顺序合并到父亲子树时，并不是独立的，只要保证每个儿子加边的相对顺序相对不变，就可以混合搭配。 举个栗子，点 $x$ 有 $k$ 个儿子$y_1 \sim y_k$，现在处理到里 $x$ 的第 $i$ 个儿子 $y_i$，其中 $y_1 \sim y_{i-1}$ 的加边顺序之一为 ${1,2}$，而 $y_i$ 子树的加边顺序之一为 $3,4$。那么有以下混合方式 $1 \quad 2 \quad \color{red}{3 \quad 4} \color{red}{3 \quad 4} \color{black}{\quad 1 \quad 2} 1 \color{red}{\quad 3} \color{black}{\quad 2} \color{red}{\quad 4} \color{red}{3} \color{black}{\quad 1} \color{red}{\quad 4} \color{black}{\quad 2} \color{red}{3} \color{black}{\quad 1 \quad 2} \quad \color{red}{4} 1 \quad \color{red}{3 \quad 4} \color{black}{\quad 2}

在处理到 y 时，f_x 已经是若干个儿子子树的所有加边顺序了。所以再乘上一个数，该数为将 y 与之前若干个儿子子树的加边顺序合并，保证 y 子树加边相对位置不变的方案数。

若处理到儿子 y 时，x 子树的边数为 sz_x，这里的 sz_x 不是处理完 x 所有儿子后的边数，而是处理到儿子 y 时的边数。问题可以转换成在 sz_y 个不同盒子里面放 sz_x - sz_y 个相同球，可以不放，求方案数。根据插板法，方案数为 C_{sz_y}^{sz_x}，这个东东预处理一下即可。

最后 ans 要除以二，因为每一条边会在它两个端点作为父亲时第一个加入。因为 ans 是将所有点为根的答案加起来，所以除以二要用逆元。

时空复杂度为 O(n^2)。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N  = 2000 + 5, p = 1e9 + 7;
inline int read() {
    int X = 0,w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48),ch = getchar();
    return w ? -X : X;
}
struct edge{
    int to, nxt;
}e[N];
int head[N], tot; 
void addedge(int x, int y) {
    e[++tot].to = y, e[tot].nxt = head[x], head[x] = tot;
}
int c[N][N], f[N], sz[N], n, ans;
void dfs(int x, int fa) {
    f[x] = 1, sz[x] = 0;
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y != fa) {
            dfs(y, x); sz[x] += sz[y];
            f[x] = f[x] * f[y] % p * c[sz[x]][sz[y]] % p;
        }
    }
    sz[x]++;
}
int ksm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res % p;
}
signed main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        addedge(x, y), addedge(y, x);
    }
    for (int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
    }
    for (int i = 1; i <= n; i++) {
        dfs(i, -1); ans = (ans + f[i]) % p;
    }
    printf("%lld\n", ans * ksm(2, p - 2) % p);
    return 0;   
}