結果

問題 No.872 All Tree Path
ユーザー tails1434
提出日時 2020-01-03 21:08:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 902 ms / 3,000 ms
コード長 957 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 453,760 KB
最終ジャッジ日時 2024-11-22 19:27:08
合計ジャッジ時間 8,751 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def main():
N = int(input())
edges = [[] for _ in range(N)]
path = []
for _ in range(N-1):
u, v, w = map(int, input().split())
u -= 1
v -= 1
edges[u].append([v,w])
edges[v].append([u,w])
path.append([u,v,w])
subtree_size = [-1] * N
def dfs(v, p):
for nv, w in edges[v]:
if nv == p:
continue
dfs(nv, v)
subtree_size[v] = 1
for c, w in edges[v]:
if c == p:
continue
subtree_size[v] += subtree_size[c]
dfs(0,-1)
ans = 0
for u, v, w in path:
if subtree_size[u] > subtree_size[v]:
ans += 2 * subtree_size[v] * (N - subtree_size[v]) * w
else:
ans += 2 * subtree_size[u] * (N - subtree_size[u]) * w
print(ans)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0