結果

問題 No.1928 Make a Binary Tree
ユーザー gew1fw
提出日時 2025-06-12 20:03:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,551 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 109,824 KB
最終ジャッジ日時 2025-06-12 20:08:23
合計ジャッジ時間 11,485 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, sys.stdin.readline().split())
        edges[x].append(y)
        edges[y].append(x)
    
    # Compute depth of each node using BFS
    depth = [0] * (N + 1)
    visited = [False] * (N + 1)
    q = deque()
    q.append(1)
    visited[1] = True
    depth[1] = 0
    max_depth = 0
    while q:
        u = q.popleft()
        for v in edges[u]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                max_depth = max(max_depth, depth[v])
                q.append(v)
    
    # Count the number of nodes at each depth
    depth_count = [0] * (max_depth + 1)
    for d in depth[1:]:  # depth[0] is for node 1, which is root
        depth_count[d] += 1
    
    # Compute count_ge[d] = number of nodes with depth >= d
    count_ge = [0] * (max_depth + 1)
    count_ge[max_depth] = depth_count[max_depth]
    for d in range(max_depth - 1, -1, -1):
        count_ge[d] = depth_count[d] + count_ge[d + 1]
    
    # Compute assign_count
    assign_count = [0] * (max_depth + 1)
    sum_assigned = 0
    for d in range(max_depth, -1, -1):
        available = count_ge[d] - sum_assigned
        cap = 1 << d  # 2^d
        assign = min(cap, available)
        assign_count[d] = assign
        sum_assigned += assign
    
    print(sum_assigned)

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