Wa On #5 寄
查看原帖
Wa On #5 寄
307535
Custlo0793楼主2022/9/22 13:47

#173020747

#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;

const int N = 2e6 + 5, MOD = 1e9 + 7;
// f[i] -> \leq 1


int n, f[N], g[N];
int pref[N], suff[N];
vector <int> son[N];

inline void dfs (int u, int fa) {
	f[u] = 1;
	for (auto v : son[u]) 
		if (v != fa) dfs(v, u), f[u] = f[u] * (f[v] + 1) % MOD;
}
inline void dp (int u, int fa) {
	g[u] = 1;
	int cnt = 0, pos = 0;
	for (auto v : son[u]) {
		g[u] = g[u] * (f[v] + 1) % MOD;
		if (v != fa) pref[++ cnt] = f[v] + 1, suff[cnt] = f[v] + 1;
	}
	pref[0] = suff[0] = suff[cnt + 1] = suff[cnt + 2] = 1;
	for (int i = 1; i <= cnt; i ++) pref[i] = pref[i - 1] * pref[i] % MOD;
	for (int i = cnt; i >= 1; i --) suff[i] = suff[i + 1] * suff[i] % MOD;
	for (auto v : son[u]) 
        if (v != fa) {
		    f[u] = f[fa] + 1, pos ++;
            f[u] = f[u] * pref[pos - 1] % MOD;
		    f[u] = f[u] * suff[pos + 1] % MOD;
		    dp(v, u);
	    }
}
signed main () {
	cin >> n;
	for (int i = 2, fa; i <= n; i ++) {
		scanf("%lld", & fa);
		son[fa].pb(i), son[i].pb(fa);
	}
	dfs(1, 0), dp(1, 0);
	for (int i = 1; i <= n; i ++) printf("%lld ", g[i]);
	return 0;
}

thx

2022/9/22 13:47
加载中...