結果

問題 No.872 All Tree Path
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:49:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 641 ms / 3,000 ms
コード長 1,084 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 161,612 KB
最終ジャッジ日時 2025-03-20 20:49:36
合計ジャッジ時間 7,157 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    N = int(sys.stdin.readline())
    adj = [[] for _ in range(N + 1)]  # Using 1-based indexing

    for _ in range(N - 1):
        u, v, w = map(int, sys.stdin.readline().split())
        adj[u].append((v, w))
        adj[v].append((u, w))

    root = 1
    stack = [(root, -1, False)]
    size = [0] * (N + 1)
    edges = []
    children = [[] for _ in range(N + 1)]  # children[u] stores (child, weight)

    while stack:
        u, parent, visited = stack.pop()
        if not visited:
            stack.append((u, parent, True))
            for v, w in adj[u]:
                if v != parent:
                    stack.append((v, u, False))
                    children[u].append((v, w))
        else:
            size[u] = 1
            for v, w in children[u]:
                size[u] += size[v]
            for v, w in children[u]:
                edges.append((v, w))

    total = 0
    for v, w in edges:
        s = size[v]
        total += 2 * s * (N - s) * w

    print(total)

if __name__ == "__main__":
    main()
0