結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:24:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 804 ms / 3,000 ms |
コード長 | 790 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 307,452 KB |
最終ジャッジ日時 | 2024-11-22 00:30:58 |
合計ジャッジ時間 | 7,759 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 6)def dfs(cur, prev):if memo[cur] != -1:return memo[cur]res = 1for next_node, w in adj_list[cur]:if next_node == prev:continueres += dfs(next_node, cur)memo[cur] = resreturn resN = int(input())adj_list = [[] for _ in range(N)]edges = []for _ in range(N-1):ui, vi, wi = map(int, input().split())edges.append((ui-1, vi-1, wi))adj_list[ui-1].append((vi-1, wi))adj_list[vi-1].append((ui-1, wi))memo = [-1] * Ndfs(0, None)ans = 0for ui, vi, wi in edges:if memo[ui] > memo[vi]:ans += 2 * memo[vi] * (N - memo[vi]) * wielse:ans += 2 * memo[ui] * (N - memo[ui]) * wiprint(ans)