結果
問題 | No.1103 Directed Length Sum |
ユーザー |
![]() |
提出日時 | 2020-07-06 21:58:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,384 ms / 3,000 ms |
コード長 | 903 bytes |
コンパイル時間 | 1,072 ms |
コンパイル使用メモリ | 81,960 KB |
実行使用メモリ | 263,472 KB |
最終ジャッジ日時 | 2024-09-24 18:29:43 |
合計ジャッジ時間 | 13,438 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sysinput=sys.stdin.readlinedef I(): return int(input())def MI(): return map(int, input().split())def LI(): return list(map(int, input().split()))def main():mod=10**9+7N=I()to=[[]for _ in range(N)]P=[-1]*Nfor i in range(N-1):a,b=MI()a-=1b-=1to[a].append(b)P[b]=aL=[]LL=[]#帰り順root=0for i in range(N):if P[i]==-1:root=iL.append(root)D=[0]*Nwhile L:v=L.pop()for nv in to[v]:D[nv]=D[v]+1L.append(nv)LL.append(nv)ch=[0]*N#子を根とする木のサイズfor v in LL[::-1]:p=P[v]ch[p]+=ch[v]+1ans=0for i in range(N):ans=(ans+(D[i])*(ch[i]+1))%modprint(ans)main()