結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2022-07-07 22:09:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 651 ms / 3,000 ms |
コード長 | 754 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 174,352 KB |
最終ジャッジ日時 | 2024-12-25 03:33:23 |
合計ジャッジ時間 | 7,290 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import defaultdict, dequen = int(input())edge = defaultdict(list)for _ in range(n - 1):u, v, w = map(int, input().split())u -= 1v -= 1edge[u].append((v, w))edge[v].append((u, w))ans = 0Parents = [-1 for _ in range(n)]visited = set([0])Que = deque([0])Topo = []while Que:curr = Que.pop()Topo.append(curr)for nex, _ in edge[curr]:if nex in visited:continuevisited.add(nex)Parents[nex] = currQue.append(nex)Size = [1 for _ in range(n)]for curr in Topo[::-1]:for nex, w in edge[curr]:if nex == Parents[curr]:continueans += Size[nex] * (n - Size[nex]) * wSize[curr] += Size[nex]print(2 * ans)