結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2023-08-30 21:28:41 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 785 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 82,480 KB |
実行使用メモリ | 206,664 KB |
最終ジャッジ日時 | 2025-01-02 18:35:54 |
合計ジャッジ時間 | 7,395 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 18 |
ソースコード
# 部分木、子の数、DFS# dfs2回は必要なかったので効率的な方法でやり直す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)] = wedge_dic[(v, u)] = wchild = [0]*(N+1)visited = [0]*(N+1)import syssys.setrecursionlimit(10**7)def dfs(current):visited[current] = 1child[current] += 1for nxt in edges[current]:if visited[nxt] == 0:dfs(nxt)child[current] += child[nxt]dfs(root)#print(child)ans = 0for u, v, w in edge_list:mn = min(child[u], child[v])ans += mn*(N-mn)*w*2print(ans)