結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー tnodino
提出日時 2022-05-06 22:22:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 768 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 99,444 KB
最終ジャッジ日時 2024-07-05 23:39:40
合計ジャッジ時間 32,097 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import setrecursionlimit
setrecursionlimit(10**6)

def dfs1(pos):
    ret = 1
    for nxt in G[pos]:
        ret += dfs1(nxt)
    Dist[pos] = ret
    return ret

def dfs2(cnt, pos):
    global ans
    if len(G[pos]) == 0:
        return
    if len(G[pos]) == 1:
        dfs2(cnt+1, G[pos][0])
        return
    D = 2 + cnt
    K = []
    for nxt in G[pos]:
        K.append((Dist[nxt], nxt))
    K.sort(reverse=True)
    N = K[:D]
    M = K[D:]
    for d,n in M:
        ans -= d
    cnt = max(0, cnt-(len(N)-2))
    for d,n in N:
        dfs2(cnt, n)
    return

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)
Dist = [-1] * N
dfs1(0)
ans = N
dfs2(0, 0)
print(ans)
0