Submission #3016283
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
Submission Time | |
---|---|
Task | N - 木 |
User | okumura |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 1267 Byte |
Status | TLE |
Exec Time | 2105 ms |
Memory | 28120 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 5 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | TLE | 2105 ms | 28120 KB |
01 | TLE | 2105 ms | 27252 KB |
02 | TLE | 2105 ms | 27300 KB |
03 | TLE | 2104 ms | 27284 KB |
04 | TLE | 2105 ms | 27284 KB |
05 | TLE | 2105 ms | 27292 KB |
06 | TLE | 2105 ms | 27284 KB |
90 | AC | 17 ms | 3192 KB |
91 | AC | 17 ms | 3188 KB |