fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int NM = 5000, MOD = 1e9+7;
  7.  
  8. int n, p[NM+5], a[NM+5];
  9. vector <int> son[NM+5];
  10. int fac[NM+5], inv_fac[NM+5], inv[NM+5];
  11. int sz[NM+5], dp[NM+5];
  12. int f[NM+5][NM+5];
  13.  
  14. int binpow(int x, int k){
  15. 	int res = 1;
  16. 	while (k > 0){
  17. 		if (k&1) res = res*x%MOD;
  18. 		k >>= 1;
  19. 		x = x*x%MOD;
  20. 	}
  21. 	return res;
  22. }
  23.  
  24. void dfs(int u){
  25. 	sz[u] = 1;
  26. 	for (int v : son[u]){
  27. 		dfs(v);
  28. 		sz[u] += sz[v];
  29. 	}
  30. 	dp[u] = 1;
  31. 	for (int v : son[u]){
  32. 		dp[u] = dp[u]*dp[v]%MOD;
  33. 	}
  34. 	dp[u] = dp[u]*fac[sz[u]-1]%MOD;
  35. 	for (int v : son[u]){
  36. 		dp[u] = dp[u]*inv_fac[sz[v]]%MOD;
  37. 	}
  38. }
  39.  
  40. signed main(){
  41. 	ios_base::sync_with_stdio(0);
  42. 	cin.tie(0);
  43. 	cout.tie(0);
  44.  
  45. 	cin >> n;
  46. 	for (int i = 2; i <= n; i++){
  47. 		cin >> p[i];
  48. 		son[p[i]].push_back(i);
  49. 	}
  50. 	for (int i = 1; i <= n; i++)
  51. 		cin >> a[i];
  52.  
  53. 	fac[0] = 1;
  54. 	for (int i = 1; i <= n; i++)
  55. 		fac[i] = fac[i-1]*i%MOD;
  56. 	inv_fac[n] = binpow(fac[n], MOD-2);
  57. 	for (int i = n-1; i >= 0; i--)
  58. 		inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
  59.  
  60. 	for (int i = 1; i <= n; i++){
  61. 		inv[i] = inv_fac[i]*fac[i-1]%MOD;
  62. 	}
  63.  
  64. 	dfs(1);
  65. 	f[1][1] = dp[1];
  66. 	for (int i = 1; i < n; i++)
  67. 		for (int u = 1; u <= n; u++){
  68. 			if (f[u][i] == 0) continue;
  69. 			int cur = n-i;
  70. 			for (int v : son[u]){
  71. 				f[v][i+1] = (f[v][i+1]+f[u][i]*sz[v]%MOD*inv[n-i])%MOD;
  72. 				cur -= sz[v];
  73. 			}
  74. 			f[u][i+1] = (f[u][i+1]+f[u][i]*cur%MOD*inv[n-i])%MOD;
  75. 		}
  76. 	for (int u = 1; u <= n; u++){
  77. 		int res = 0;
  78. 		for (int i = 1; i <= n; i++)
  79. 			res = (res+f[u][i]*a[i])%MOD;
  80. 		cout << res << ' ';
  81. 	}
  82. 	return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OdFpfu
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!