Submission #11378340


Source Code Expand

M=10**9+7
N=1000
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
while s:
    v=s.pop()
    f[v]=0
    o+=v,
    l=[]
    for w in e[v]:
        if f[w]:
            l+=w,
            s+=w,
    e[v]=l
dp1,dp2=[0]*n,[0]*n
sz1,sz2=[0]*n,[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
    s=t=1
    c1,c2=[1],[1]
    for w in e[v]:
        c1+=c1[-1]*dp1[w]*inv[sz1[w]]%M,
        s+=sz1[w]
    for w in e[v][::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    dp1[v]=c1[-1]*fac[s-1]%M
    sz1[v]=s
    c[v]=c1,c2[-2::-1]
dp2[0]=sz2[0]=1
for v in o:
    c1,c2=c[v]
    for w,l,r in zip(e[v],c1,c2):
        dp2[w]=l*r*dp2[v]*inv[sz2[v]-1]*fac[sz2[v]-1+sz1[v]-sz1[w]-1]%M
        sz2[w]=sz2[v]+sz1[v]-sz1[w]
s=0
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    s+=dp1*dp2*inv[sz1-1]*inv[sz2-1]*fac[sz1+sz2-2]%M
print(s*pow(2,M-2,M)%M)

Submission Info

Submission Time
Task N - 木
User c_r_5
Language Python (3.4.3)
Score 5
Code Size 1073 Byte
Status AC
Exec Time 26 ms
Memory 3572 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 9
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 AC 26 ms 3572 KB
01 AC 25 ms 3552 KB
02 AC 26 ms 3572 KB
03 AC 26 ms 3572 KB
04 AC 26 ms 3572 KB
05 AC 26 ms 3572 KB
06 AC 26 ms 3572 KB
90 AC 18 ms 3192 KB
91 AC 18 ms 3192 KB