結果
問題 | No.872 All Tree Path |
ユーザー | FromBooska |
提出日時 | 2023-08-30 21:25:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,425 ms / 3,000 ms |
コード長 | 1,002 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 86,772 KB |
実行使用メモリ | 441,352 KB |
最終ジャッジ日時 | 2023-08-30 21:25:45 |
合計ジャッジ時間 | 14,281 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,050 ms
209,564 KB |
testcase_01 | AC | 1,070 ms
209,296 KB |
testcase_02 | AC | 1,083 ms
211,068 KB |
testcase_03 | AC | 1,425 ms
441,352 KB |
testcase_04 | AC | 81 ms
71,276 KB |
testcase_05 | AC | 1,267 ms
217,340 KB |
testcase_06 | AC | 1,123 ms
210,420 KB |
testcase_07 | AC | 1,109 ms
210,072 KB |
testcase_08 | AC | 224 ms
91,688 KB |
testcase_09 | AC | 218 ms
91,588 KB |
testcase_10 | AC | 229 ms
91,552 KB |
testcase_11 | AC | 222 ms
91,620 KB |
testcase_12 | AC | 254 ms
91,576 KB |
testcase_13 | AC | 73 ms
71,212 KB |
testcase_14 | AC | 72 ms
70,972 KB |
testcase_15 | AC | 72 ms
71,148 KB |
testcase_16 | AC | 72 ms
71,048 KB |
testcase_17 | AC | 72 ms
71,320 KB |
testcase_18 | AC | 74 ms
71,208 KB |
testcase_19 | AC | 74 ms
71,428 KB |
ソースコード
N = int(input()) edge_list = [] edge_dic = {} edges = [[] for i in range(N+1)] for i in range(N-1): u, v, w = map(int, input().split()) edges[u].append(v) edges[v].append(u) edge_list.append((u, v, w)) edge_dic[(u, v)] = w edge_dic[(v, u)] = w child = [0]*(N+1) visited = [0]*(N+1) import sys sys.setrecursionlimit(10**7) def dfs(current): visited[current] = 1 child[current] += 1 for nxt in edges[current]: if visited[nxt] == 0: dfs(nxt) child[current] += child[nxt] for i in range(1, N+1): if len(edges[i]) == 1: root = i break dfs(root) #print(child) def dfs2(current, prev): global ans for nxt in edges[current]: if nxt != prev: #print('current', current, 'nxt', nxt, child[nxt], (N-child[nxt]), edge_dic[(current, nxt)]) ans += child[nxt]*(N-child[nxt])*edge_dic[(current, nxt)] dfs2(nxt, current) ans = 0 dfs2(root, 0) print(ans*2)