結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー 山本信二
提出日時 2022-04-29 13:36:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 953 bytes
コンパイル時間 81 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 43,648 KB
最終ジャッジ日時 2024-06-28 20:47:26
合計ジャッジ時間 12,996 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
node = [[] for _ in range(n)]  # 隣接リスト
e = []
for i in range(n - 1):
    x, y = map(int, input().split())
    e.append((x - 1, y - 1))
    node[x - 1].append(y - 1)
    node[y - 1].append(x - 1)

from collections import deque

mod = 10 ** 9 + 7
p = [-1] * n  # p[i] はi の親。根なら-1
q = deque([0])  # 根はどこでも良い
r = []  # トポロジカルソート.根から浅い順番にソートされて入っている

dp = [1] * n

# dfs ：　トポロジカルソートと葉ノードのdp初期化
while q:
    i = deque.popleft(q)
    r.append(i)
    # print(node[i])
    for a in node[i]:  # i の子node を探索する
        if p[a] != -1:
            continue
        p[a] = i
        node[a].remove(i)  # 子への頂点のみを持つ
        deque.append(q, a)
  

for i in r[::-1]:  # 葉ノードから順番にdpを埋める
    for j in node[i]:
        dp[i] = max(dp[j],n-1-dp[j])
print(dp[0])
0