結果
問題 |
No.1928 Make a Binary Tree
|
ユーザー |
![]() |
提出日時 | 2022-05-08 15:59:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,410 ms / 3,000 ms |
コード長 | 1,142 bytes |
コンパイル時間 | 94 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 107,008 KB |
最終ジャッジ日時 | 2024-07-08 04:19:18 |
合計ジャッジ時間 | 40,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
from sys import setrecursionlimit setrecursionlimit(10**6) from heapq import heappop,heappush def dfs(pos, pre): global G, Vec for nxt in G[pos]: if nxt == pre: continue P = dfs(nxt, pos) heappush(Vec[pos], -P) M = len(Vec[pos]) idx = pos for nxt in G[pos]: if nxt == pre: continue if len(Vec[nxt]) > M: M = len(Vec[nxt]) idx = nxt if idx != pos: while Vec[pos]: heappush(Vec[idx], heappop(Vec[pos])) for nxt in G[pos]: if nxt == pre: continue if nxt == idx: continue while Vec[nxt]: heappush(Vec[idx], heappop(Vec[nxt])) Vec[pos] = Vec[idx] ret = 1 if len(Vec[pos]) <= 2: while Vec[pos]: ret += -heappop(Vec[pos]) else: for _ in range(2): ret += -heappop(Vec[pos]) return ret 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) G[y].append(x) Vec = [[] for _ in range(N)] print(dfs(0, -1))