結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2022-05-17 23:14:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 3,000 ms |
コード長 | 649 bytes |
コンパイル時間 | 381 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 151,552 KB |
最終ジャッジ日時 | 2024-09-15 21:54:37 |
合計ジャッジ時間 | 8,745 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import dequen = int(input())e = [[] for i in range(n)]for _ in range(n-1):u,v,w = map(int,input().split())u,v = u-1,v-1e[u].append([v,w])e[v].append([u,w])ans = 0par = [-1]*nvis = [0]*nvis[0] = 1q = deque([0])topo = []while q:now = q.pop()topo.append(now)for nex,_ in e[now]:if vis[nex]:continuevis[nex] = 1par[nex] = nowq.append(nex)size = [1]*nfor now in topo[::-1]:for nex,w in e[now]:if nex == par[now]:continueans += size[nex]*(n-size[nex])*wsize[now] += size[nex]print(ans*2)