結果

問題 No.1418 Sum of Sum of Subtree Size
コンテスト
ユーザー koheijkt
提出日時 2026-01-13 18:03:30
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 623 ms / 2,000 ms
コード長 1,156 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 288 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 185,616 KB
最終ジャッジ日時 2026-01-13 18:03:48
合計ジャッジ時間 10,665 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, math
sys.setrecursionlimit(10**8)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
N = int(input())
G = [list() for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


size = [1] * (N + 1)
size[0] = 0

# 部分木のサイズ
def dfs(pos, pre):
    for nex in G[pos]:
        if nex == pre:
            continue
        dfs(nex, pos)
        # 戻ったときに親に計上する
        size[pos] += size[nex]
    return

dfs(1, 0)

# 各頂点がyになるときの寄与を考える
def dfs2(pos, pre):
    # (1) x が pos の部分木に含まれない頂点のとき
    #  (N - size[pos]) * size[pos] # スコア * 寄与回数
    # (2) x が pos の部分木に含まれる
    res1 = (N - size[pos]) * size[pos]
    res2 = N # (3) f(pos, pos) 分
    for nex in G[pos]:
        if nex == pre:
            continue
        # (N - size[子ども]) * size[子ども]
        res1 += (N - size[nex]) * size[nex]
        # 再帰的に res に追加
        res2 += dfs2(nex, pos)
    #print(pos, res1, res2)
    return res1 + res2

ans = dfs2(1, 0)
print(ans)
0