自动搬运

查看原文

来自洛谷，原作者为

	Guosn ”了KA我“：CZZ

搬运于2025-08-24 22:53:54，当前版本为作者最后更新于2025-08-19 11:24:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置芝士

• 将 $k$ 个数插入到 $m$ 个数中，方案数为 $\binom{m + k}{k}$，相当于从 $m + k$ 个数中拿 $k$ 个。
• 一棵树的拓扑序个数是 $n!\over \prod sz_u$。对于一棵树有 $n!$ 种的排列，因为对于一个点 $u$ 他必须在它子树内的点前面，所以只有 $sz_u-1!$ 种的排列，相当于除以 $sz_u$，从根往下递归，总共除以 $\prod sz_u$

题解

下文中所指 $u$ 的子树含 $u$。

发现一个点的拓扑序，只与他的父亲有关，所以考虑从上往下转移。设 $f_{u,i}$，表示不考虑 $u$ 子树内的点，其他点都已经考虑完了，$u$ 的拓扑序是 $i$ 的方案数。

DP 转移：
当从 $f_{u,j}$ 转移到 $f_{v,i}$ 时，要将除了 $v$ 以外的拓扑序安排好，相当将 $sz_u-sz_v-1$ 个点（$u$ 已经安排好了），插入到已经确定的 $n - sz_u + 1$ 个拓扑序中，但又因为子树的拓扑序比 $u$ 的大，所以只有 $n - sz_u + 1 -j$ 个点可以插，插完后再分配拓扑序。
即（其中 $k$ 是 $v$ 子树以外的节点） ：

$$f_{v,i} = \sum_{j = 1} ^{i - 1} f_{u,j} \times \binom{n - sz_u - j + 1 + sz_u-sz_v-1}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k} $$

化简后：

$$f_{v,i} = \sum_{j = 1} ^{i - 1} f_{u,j} \times \binom{n -sz_v- j}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k} $$

统计答案：
计算点 $i$ 的答案时，要将其子树内 $sz_i - 1$ 的点插入到已经确定的 $n - sz_i + 1$ 个已经确定的拓扑序种，而且还要比 $i$ 的拓扑序大，故（$v$ 是 $u$ 子树内的点）：

$$ans_i = \sum_{j = 1} ^n b_j\times f_{i,j}\times \binom{n - sz_i + 1 - j + sz_i - 1}{sz_i - 1} \times \frac{sz_i!}{\prod sz_v} $$

化简：

$$ans_i = \sum_{j = 1} ^n b_j\times f_{i,j}\times \binom{n - j}{sz_i - 1} \times \frac{sz_i!}{\prod sz_v} $$

时间复杂度 $O(n^3)$ 考虑优化：$f_{v,i}$ 只比 $f_{v,i - 1}$ 多了 $f_{u,i - 1} \times \binom{n -sz_v- (i - 1)}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k}$ 可以前缀和优化。
时间复杂度 $O(n^2)$。
注意 ，要判断数组越界，组合数要取模（可能很大）。

code

#include<bits/stdc++.h>
#define N 5010
#define int long long
#define pb push_back
#define md 1000000007
#define Fo(a, b) for(auto a : b) 
#define fo(a, b, c) for(int b = a; b <= c; b++)
#define _fo(a, b, c) for(int b = a; b >= c; b--)
using namespace std;
int n, b[N], fac[N], sz[N], prod[N], C[N][N], f[N][N], ans[N];
vector<int>G[N]; 
int fast(int a, int p){
	int s = 1;
	while(p){
		if(p & 1) s = s * a % md;
		a = a * a % md;
		p >>= 1;
	}
	return s;
}
void init(){
	fac[0] = 1;
	fo(1, i, 5000) fac[i] = fac[i - 1] * i % md; 
	fo(0, i, n) C[i][0] = 1;
	fo(1, i, n) fo(1, j, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
	prod[0] = 1, f[1][1] = 1;
}
void dfs(int u){
	sz[u] = prod[u] = 1;
	Fo(v, G[u]){
		dfs(v); 
		sz[u] += sz[v], prod[u] = prod[u] * prod[v] % md; 
	}
	prod[u] = prod[u] * fast(sz[u], md - 2) % md;
}
void calc(int v, int u){
	int tp = fac[sz[u] - sz[v] - 1];
 	Fo(cur, G[u]){
		if(v == cur) continue;
		tp = tp * prod[cur] % md;
	}
//	cout << "u;" << u << ' ' << "v:" << v << ' ' << "tp:" << tp << "\n";
	fo(1, i, n){
		if(n - sz[v] - i + 1 >= 0) f[v][i] = (f[v][i - 1] + f[u][i - 1] * C[n - sz[v] - i + 1][sz[u] - sz[v] - 1] % md * tp % md) % md;
	}
}
void solve(int u){
	Fo(v, G[u]){
		calc(v, u), solve(v);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	fo(2, i, n){
		int fa; cin >> fa;
		G[fa].pb(i);
	}
//	fo(1, i, n){
//		Fo(v, G[i]) cout << v << ' ';
//		cout << "\n";
//	}
	fo(1, i, n) cin >> b[i];
	init();
	//cout << C[4][2] << ' ';
	dfs(1), solve(1);
	//fo(1, i, n) cout << prod[i] << ' '; 
	fo(1, i, n) fo(1, j, n) 
		if(n >= j) ans[i] = (ans[i] + b[j] * f[i][j] % md * C[n - j][sz[i] - 1] % md * fac[sz[i]] % md * prod[i] % md) % md;
	fo(1, i, n) cout << ans[i] << ' ';
	return 0;
}