結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:54:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 750 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 102,288 KB |
最終ジャッジ日時 | 2024-10-07 01:35:22 |
合計ジャッジ時間 | 5,818 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
import sysinput = sys.stdin.readlineN=int(input())E=[[] for i in range(N+1)]for i in range(N-1):a,b=map(int,input().split())E[a].append(b)E[b].append(a)ROOT=1QUE=[ROOT]Parent=[-1]*(N+1)Parent[ROOT]=0 # ROOTの親を定めておく.TOP_SORT=[] # トポロジカルソートwhile QUE: # トポロジカルソートと同時に親を見つけるx=QUE.pop()TOP_SORT.append(x)for to in E[x]:if Parent[to]==-1:Parent[to]=xQUE.append(to)Children=[1]*(N+1)for x in TOP_SORT[::-1]: #(自分を含む)子ノードの数を調べるChildren[Parent[x]]+=Children[x]ANS=N*Nfor i in range(1,N+1):x=Children[i]-1y=N-x-1ANS+=(x+1)*y+y*(x+1)print(ANS)