AtCoder Beginner Contest 160

https://atcoder.jp/contests/abc160

F - Distributing Integers

 

题意：给定一棵树，选定一个点作为初始点，赋值 $1$，对于 $2$ 到 $n$，可以赋值给任意与已赋值点相邻的点，问以每个点作为初始点时各有多少种赋值方式。

数论+树形dp+换根dp

先考虑固定根的情况下求赋值方式数。

以 $u$ 为根的子树的赋值结果是u的子孙节点的排列，假设 $u$ 共有 $C$ 个子孙节点，则第一个子节点的子树的赋值结果可以选 $c$ 个位置中的几个放入，其内部的顺序就是该子树的赋值结果，可以递归得到。而 $u$ 的所有子节点都选好位置后，就构成了 $u$ 的赋值结果。

所以这是一个可重排列的问题，从 $C$ 个位置中选择 $c_1$ 个位置放第一个子节点， $c_2$ 个位置放第二个子节点，······，而对于各个子节点内部是怎样的顺序，我们并不关心，所以就是 $\frac{C!}{c_1!\cdot c_2!\cdots c_k!}$。再乘以各个子节点的递归值，就是u的值。

再考虑换根。

假设 $u$ 为根，现在要求 $ans[v]$，则要把 $u$ 变成 $v$ 的子节点，乘到 $v$ 的答案里去，但是由于之前 $v$ 是 $u$ 的子节点，所以要先把 $v$ 从 $u$ 的子节点中去掉，就是乘以 $\frac{(C-c_v)!\cdot c_v!}{C!\cdot dp[v]}$，也就是 $\frac{1}{Comb(C,C_v)\cdot dp[v]}$，之后再把 $v$ 视为根，一次更新 $v$ 的子节点即可，注意由于始终把 $u$ 作为根，所以子节点数始终是 $n-1$。

或者考虑 $Comb(c_1,c_1)dp[1]\cdot Comb(c_1+c_2,c_2)dp[2]\cdots Comb(c_1+c_2+\cdots c_k,c_k)dp[k]$，与 $\frac{C!}{c_1!\cdot c_2!\cdots c_k!}dp[1]dp[2]\cdots dp[k]$ 也是一样的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
ll fac[N], inv[N];
ll power(ll a, ll x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
ll C(ll n, ll k) {
	return fac[n] * inv[k] % mod*inv[n - k] % mod;
}
vector<int>G[N];
ll dp[N], ans[N], cnt[N];
void dfs1(int u, int _fa) {
	cnt[u] = dp[u] = 1;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs1(v, u);
		cnt[u] += cnt[v];
		dp[u] = dp[u] * dp[v] % mod * C(cnt[u] - 1, cnt[v]) % mod;
	}
}
void dfs2(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		ans[v] = ans[u] * power(dp[v] * C(n - 1, cnt[v]) % mod, mod - 2) % mod;
		ans[v] = ans[v] * dp[v] % mod*C(n - 1, n - cnt[v]) % mod;
		dfs2(v, u);
	}
}
int main() {
	init();
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	ans[1] = dp[1];
	dfs2(1, 0);
	for (int i = 1; i <= n; i++)printf("%lld\n", ans[i]);
	return 0;
}