Submission #3016281

---

Source Code Expand

import sys
sys.setrecursionlimit(10**8)
N=int(input())
table=[set() for i in range(N)]
L=[]
for i in range(N-1):
    a,b=map(int,input().split())
    table[a-1].add(b-1)
    table[b-1].add(a-1)
    L.append((a-1,b-1))
#mod table!
mod=10**9+7
frac=[1]*(N+2)
rfrac=[1]*(N+2)
s=1
t=1
for i in range(2,N+2):
    s*=i
    s%=mod
    frac[i]=s
    t*=pow(i,mod-2,mod)
    t%=mod
    rfrac[i]=t
#Tree dp
def count(granpa,parent):
    for i in table[parent]:
        if i==granpa:
            continue
        count(parent,i)
    for i in table[parent]:
        if i==granpa:
            continue
        vn[granpa][parent]+=1+vn[parent][i]
    dp[granpa][parent]*=frac[vn[granpa][parent]]
    for i in table[parent]:
        if i==granpa:
            continue
        dp[granpa][parent]*=rfrac[vn[parent][i]+1]*dp[parent][i]
        dp[granpa][parent]%=mod
    return vn[granpa][parent],dp[granpa][parent]
#answer
ans=0
for x,y in L:
    dp=[[1]*N for i in range(N)]
    vn=[[0]*N for i in range(N)]
    a,b=count(x,y)
    dp=[[1]*N for i in range(N)]
    vn=[[0]*N for i in range(N)]
    c,d=count(y,x)    
    s=frac[a+c]
    s*=rfrac[a]*rfrac[c]
    s%=mod
    s*=b*d
    s%=mod
    ans+=s
    ans%=mod
print(ans)

Submission Info

Judge Result