Atcoder [ABC160F] Distributing Integers 题解 [ 蓝 ] [ 有向树拓扑序计数 ] [ 换根 DP ]

Distributing Integers

一个经典结论 + 换根 DP 的题。

结论 \(1\)：对于任意一颗有向树，无论是内向还是外向的，其拓扑序个数都是 \(\dfrac{n!}{\prod_{i = 1}^{n}size_i}\)。

结论 \(\bm 1\) 证明：

这里以内向树为例（外向树也是同理），考虑计数转概率，设拓扑序合法的概率为 \(P\)，则拓扑序总方案数为 \(P\times n!\)。

对每个节点的限制分别考虑，对于一个节点 \(u\)，其限制就是子树内的所有节点的拓扑序都在 \(\bm u\) 的拓扑序前。因此这一条限制的合法概率为 \(\dfrac{(size_u - 1)!}{size_u!} = \dfrac{1}{size_u}\)。

显然每一条限制是互相独立的，于是将他们相乘即可得到概率 \(P = \dfrac{1}{\prod_{i = 1}^{n}size_i}\)。因此总方案数为 \(\dfrac{n!}{\prod_{i = 1}^{n}size_i}\)。

这启示我们可以从子树大小的角度求解问题。剩下的就很显然了，我们先做一遍普通树形 DP 求解以 \(1\) 为根的结果，然后注意到根节点从 \(u\) 移动到 \(v\)，子树大小受到影响的只有 \(\bm{u, v}\) 两个点，于是考虑换根 DP，转移的时候将他们的贡献去掉，重新算一遍即可。

使用线性预处理逆元，即可做到时间复杂度 \(O(n)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 200005;
const ll mod = 1e9 + 7;
vector<int> g[N];
int n;
ll inv[N], prod = 1, sz[N], dp[N];
void init()
{inv[1] = 1;for(int i = 2; i < N; i++)inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
void dfs1(int u, int fa)
{sz[u] = 1;for(auto v : g[u]){if(v == fa) continue;dfs1(v, u);sz[u] += sz[v];}prod = (prod * inv[sz[u]]) % mod;
}
void dfs2(int u, int fa)
{for(auto v : g[u]){if(v == fa) continue;dp[v] = (dp[u] * sz[v] % mod * inv[n - sz[v]]) % mod;dfs2(v, u);}
}
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cin >> n;for(int i = 1; i <= n; i++) prod = (prod * i) % mod;for(int i = 1; i < n; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}    dfs1(1, 0);dp[1] = prod;dfs2(1, 0);for(int i = 1; i <= n; i++) cout << dp[i] << "\n";return 0;
}