悬关求调
查看原帖
悬关求调
525375
Richard_Whr楼主2023/8/24 15:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=4e5+10,mod=1e9+7;
int h[N],e[M],ne[M],idx;
int n;
int f[N];
int g[N];
vector<int> pre[N],suf[N];
int idson[N];
int fson[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs1(int u,int fa)
{
	f[u]=1;
	int cnt=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int son=e[i];
		if(son==fa) continue;
		dfs1(son,u);
		cnt++;
		fson[cnt]=f[son]+1;
		f[u]=(f[u]*(f[son]+1))%mod;
	}
	pre[u].resize(cnt+2);
	suf[u].resize(cnt+2);
	pre[u][0]=1;
	for(int i=1;i<=cnt;i++)
	{
		pre[u][i]=(pre[u][i-1]*fson[i])%mod;
	}
	suf[u][cnt+1]=1;
	for(int i=cnt;i>=1;i--)
	{
		suf[u][i]=(suf[u][i+1]*fson[i])%mod;
	}
}

void dfs2(int u,int fa)
{
	int cnt=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int son=e[i];
		if(son==fa) continue;
		cnt++;
		g[son]=(g[u]+1)*pre[u][cnt-1]%mod*suf[u][cnt+1]%mod;
		dfs2(son,u);
	}
}

signed main()
{
	memset(h,-1,sizeof h);
	
	scanf("%lld",&n);
	
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%lld",&x);
		add(x,i),add(i,x);
	}
	
	dfs1(1,-1);
	
	g[1]=0;
	
	dfs2(1,-1);
	
	//for(int i=1;i<=n;i++) printf("%d\n",h[i]);
	
	for(int i=1;i<=n;i++) printf("%lld ",(g[i]+1)*f[i]%mod);
}

2023/8/24 15:59
加载中...