Submission #11378349


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 PyPy3 (2.4.0)
Score 5
Code Size 1073 Byte
Status AC
Exec Time 201 ms
Memory 39920 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 190 ms 39920 KB
01 AC 184 ms 39152 KB
02 AC 190 ms 39792 KB
03 AC 194 ms 39792 KB
04 AC 193 ms 39792 KB
05 AC 193 ms 39792 KB
06 AC 201 ms 39920 KB
90 AC 167 ms 38256 KB
91 AC 168 ms 38496 KB