题目描述

难度分:$2048$

输入$n(2 \leq n \leq 2 \times 10^5)$和一棵无向树的$n-1$条边，节点编号从$1$到$n$。

定义$f(i)$为如下过程的方案数：

• 首先，在节点$i$写下数字$1$。
• 然后，选择一个与写下数字节点相邻的节点（没有写过数字），写下数字$2$。

继续，重复上述过程，依次写下数字$3,4,…,n$。

输出$f(1),f(2),…,f(n)$。

输入样例$1$

3
1 2
1 3

输出样例$1$

2
1
1

输入样例$2$

2
1 2

输出样例$2$

1
1

输入样例$3$

5
1 2
2 3
3 4
3 5

输出样例$3$

2
8
12
3
3

输入样例$4$

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

输出样例$4$

40
280
840
120
120
504
72
72

算法

换根DP

先考虑$f(1)$怎么算，如果从$1$开始DFS遍历这棵树，按顺序记录遍历到的数字，会得到一个$1$~$n$的排列，总共有$n!$ 种，其中肯定有不合法的。

比如，这个排列肯定要以$1$开头，所有不以$1$开头的排列都是不合法的。以$1$开头的排列个数是$(n-1)!$（剩下的$n-1$个数全排列），相当于把$n!$除以$n$。

同理，对于每棵子树$v$而言（对应着$1$~$n$排列中的一个子序列），不以$v$的标记数字开头的排列都是不合法的，同样要把方案数除以$sz[v]$，即子树$v$的大小。

所以$f(1)=\frac{n!}{sz[1] \times sz[2] \times … \times sz[n]}$。

对于其他$f(i)$，我们可以在$f(1)$的基础上，用换根DP快速计算上式的分母。从节点$u$换到节点$v$，$f[u]$先除以$sz[v]$，对于不在子树$v$中的节点，会形成一棵$v$为根节点朝上的子树，所以要乘以$(n-size[v])$。

上述过程中有除法同余，可以用费马小定理计算逆元。

复杂度分析

时间复杂度

对整棵树进行两次DFS（一次求$f[1]$，一次换根求$f[u](u \gt 1)$）就能得到答案。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

$sz$数组和$f$数组是线性的，为$O(n)$。预处理逆元需要三个辅助数组，均与$n$相关，空间消耗也是$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 1e9 + 7;
vector<int> graph[N];
int n, sz[N], f[N];
LL inv[N], finv[N], fac[N];

void get_inv(int n) {
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = (MOD - MOD/i) * inv[MOD % i] % MOD;
    }
    finv[0] = finv[1] = fac[0] = fac[1] = 1;
    for(int i = 2; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

int fast_power(int a, int k, int p) {
    int res = 1 % p;
    while(k) {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


void dfs(int u, int fa) {
    sz[u] = 1;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    f[1] = 1LL * f[1] * sz[u] % MOD;
}

void reroot(int u, int fa) {
    for(int v: graph[u]) {
        if(v == fa) continue;
        f[v] = 1LL * f[u] * fast_power(sz[v], MOD - 2, MOD) % MOD * (n - sz[v]) % MOD;
        reroot(v, u);
    }
}

int main() {
    if(!inv[0]) get_inv(N - 10);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    f[1] = 1;
    dfs(1, 0);
    reroot(1, 0);
    for(int i = 1; i <= n; i++) {
        printf("%d\n", fac[n] * fast_power(f[i], MOD - 2, MOD) % MOD);
    }
    return 0;
}