QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#508516#7792. Tree Topological Order CountingDaiRuiChen0070 93ms16404kbC++171.3kb2024-08-07 16:42:272024-08-07 16:42:27

Judging History

你现在查看的是最新测评结果

  • [2024-08-07 16:42:27]
  • 评测
  • 测评结果:0
  • 用时:93ms
  • 内存:16404kb
  • [2024-08-07 16:42:27]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005,MOD=1e9+7;
ll ksm(ll a,ll b=MOD-2) {
	ll ret=1;
	for(;b;a=a*a%MOD,b>>=1) if(b&1) ret=ret*a%MOD;
	return ret;
}
vector <int> G[MAXN];
int n,fa[MAXN],siz[MAXN],a[MAXN];
ll fac[MAXN],inv[MAXN],ifac[MAXN],g[MAXN],ig[MAXN],f[MAXN][MAXN],ans[MAXN];
ll C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
void dfs0(int u) {
	siz[u]=g[u]=ig[u]=1;
	for(int v:G[u]) {
		dfs0(v),siz[u]+=siz[v];
		g[u]=g[u]*g[v]%MOD;
	}
	g[u]=g[u]*inv[siz[u]]%MOD;
	ig[u]=ig[u]*siz[u]%MOD;
}
void dfs1(int u) {
	ans[u]=fac[siz[u]]*g[u]%MOD*f[u][1]%MOD;
	for(int v:G[u]) {
		ll w=fac[siz[u]-siz[v]-1]*g[u]%MOD*ig[v]%MOD*siz[u]%MOD;
		for(int k=2;k<=siz[u];++k) for(int i=max(1,k-siz[u]+siz[v]);i<=siz[v]&&i<k;++i) {
			f[v][i]=(f[v][i]+f[u][k]*w%MOD*C(k-2,i-1)%MOD*C(siz[u]-k,siz[v]-i))%MOD;
		}
		dfs1(v);
	}
}
signed main() {
	scanf("%d",&n);
	for(int i=fac[0]=ifac[0]=1;i<=n;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD),inv[i]=ksm(i);
	for(int i=2;i<=n;++i) scanf("%d",&fa[i]),G[fa[i]].push_back(i);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	dfs0(1);
	for(int i=1;i<=n;++i) f[1][i]=a[i];
	dfs1(1);
	for(int i=1;i<=n;++i) printf("%lld ",ans[i]); puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4068kb

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:

132551152 41677919 102495837 551247922 120000529 379839125 398510240 518510769 379839125 518510769 

result:

wrong answer 2nd numbers differ - expected: '750202542', found: '41677919'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 93ms
memory: 16404kb

input:

3000
1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...

output:

16671810 327085511 954611734 991915797 246024471 819506667 440190361 921261170 121769963 977066023 27455643 666529375 479362885 921821860 392703848 766133421 133335504 968612682 199685361 440344548 329645679 508611620 268487003 101941549 378536289 169449008 288736252 783267323 185632991 164728028 24...

result:

wrong answer 2nd numbers differ - expected: '944499931', found: '327085511'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%