算法
(全方位木DP/换根DP) $O(N)$
假设我们固定了填有 $1$ 的节点,并以这个节点作为这颗树的根节点。 所有有效的填写数字的方式都应满足以下性质:
- 在节点 $v$ 的父节点上填写的数字应该比在节点 $v$ 处填写的数字小
这相当于所有边的方向向下,然后计算拓扑排序的数量。
记 $dp[v]$ 为以节点 $v$ 为根的子树的拓扑排序的数量,$t[v]$ 为为以节点 $v$ 为根的子树的节点个数。
$dp[v]$ 可以通过以下递推式算出:
$$dp[v] = \frac{(t[v] - 1)!}{\prod\limits_{c \in v \text{の子}}t[c]!} \cdot \prod_{c \in v \text{の子}} dp[c]$$
通过全方位木DP,我们可以在 $O(N)$ 时间内解决本题。
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int MX = 200005;
vector<int> to[MX];
using mint = modint1000000007;
// combination mod prime
const int mod = 1000000007;
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} comb(MX);
struct DP {
mint dp;
int t;
DP(mint dp = 1, int t = 0): dp(dp), t(t) {}
DP operator+(const DP& a) {
return DP(dp * a.dp * comb(t+a.t, t), t + a.t);
}
DP addRoot() const {
return DP(dp, t + 1);
}
};
vector<DP> dp[MX];
DP ans[MX];
DP dfs(int v, int p = -1) {
// dpSum = DP(1, 0);
DP dpSum;
dp[v] = vector<DP>(to[v].size());
rep(i, to[v].size()) {
int u = to[v][i];
if (u == p) continue;
dp[v][i] = dfs(u, v);
dpSum = dpSum + dp[v][i];
}
return dpSum.addRoot();
}
void bfs(int v, const DP& dpP = DP(), int p = -1) {
int deg = to[v].size();
rep(i, deg) if (to[v][i] == p) dp[v][i] = dpP;
vector<DP> dpLeft(deg + 1);
rep(i, deg) dpLeft[i + 1] = dpLeft[i] + dp[v][i];
vector<DP> dpRight(deg + 1);
for (int i = deg - 1; i >= 0; --i)
dpRight[i] = dpRight[i + 1] + dp[v][i];
ans[v] = dpLeft[deg].addRoot();
rep(i, deg) {
int u = to[v][i];
if (u == p) continue;
DP d = dpLeft[i] + dpRight[i + 1];
bfs(u, d.addRoot(), v);
}
}
int main() {
int n;
cin >> n;
rep(i, n - 1) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
dfs(0);
bfs(0);
rep(i, n) {
cout << ans[i].dp.val() << '\n';
}
return 0;
}
…虽然还没学,但是感觉这道题好难处理