結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:13:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,134 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 215,980 KB
最終ジャッジ日時 2025-05-14 13:14:13
合計ジャッジ時間 15,095 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 29 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set higher recursion depth limit for safety, potentially needed for deep call stacks in Python even without explicit recursion.
# Try setting it, catch exception if system limits prevent it.
try:
    # Set recursion depth to a large value, N=2e5 might lead to deep call stacks in some Python versions/setups
    # Adjusted based on typical competitive programming limits and N
    sys.setrecursionlimit(200010 + 10) 
except OverflowError:
    pass # Keep default limit if setting higher value fails

def solve():
    N = int(sys.stdin.readline())
    
    # Using dictionary for adjacency list. This works well for potentially non-contiguous node IDs
    # although problem states 1..N. Dictionary is generally safe.
    adj = {} 

    if N == 1:
        print(1)
        return

    # Read edges and build adjacency list for undirected graph
    for _ in range(N - 1):
        u, v = map(int, sys.stdin.readline().split())
        # Ensure nodes exist as keys before appending
        if u not in adj: adj[u] = []
        if v not in adj: adj[v] = []
        adj[u].append(v)
        adj[v].append(u)

    # Parent dictionary to store parent of each node in the rooted tree
    parent = {} 
    # Depth dictionary to store depth of each node from the root
    depth = {}  
    
    # Use BFS to establish parent pointers and depths starting from root 1
    q = [(1, 0)] # Queue stores tuples of (vertex, depth)
    visited = {1}
    parent[1] = 0 # Use 0 as a sentinel value indicating root has no parent
    depth[1] = 0
    
    # List to store nodes along with their depths, to be sorted later
    nodes_to_process_order = [] 

    head = 0 # Use list as a queue with manual head index management for performance
    while head < len(q):
        curr_v, curr_d = q[head]
        head += 1
        
        # Add node and its depth to the list for sorting
        nodes_to_process_order.append((curr_d, curr_v))

        # Explore neighbors
        if curr_v in adj:
            for neighbor in adj[curr_v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    parent[neighbor] = curr_v
                    depth[neighbor] = curr_d + 1
                    q.append((neighbor, curr_d + 1))

    # Sort nodes primarily by depth descending. If depths are equal, sort by vertex ID ascending as a tiebreaker.
    # This ensures that deeper nodes are processed first.
    nodes_to_process_order.sort(key=lambda x: (-x[0], x[1]))

    # Initialize available parent slots for each node. 
    # Using a list is efficient for 1..N indexing. Size N+1 for 1-based indexing.
    # Each node can initially be a parent to at most 2 children.
    slots = [2] * (N + 1) 
    
    # Counter for nodes that successfully find a parent
    matched_count = 0 

    # Process nodes according to the sorted order (deepest first)
    for d, v in nodes_to_process_order:
        if v == 1: # The root node does not need a parent
            continue

        # Start searching for an available ancestor, beginning from the direct parent `p = parent[v]`
        curr = parent.get(v, 0) # Use .get for robustness, default to 0 if v not in parent map (should not happen in connected tree)
        
        # Iterate upwards through ancestors until root's pseudo parent 0 is reached
        while curr != 0: 
            # Check if the current ancestor `curr` has available slots
            if slots[curr] > 0: 
                slots[curr] -= 1 # Assign vertex v to this ancestor, decrement slot count
                matched_count += 1 # Increment count of vertices successfully assigned a parent
                # Parent found for v, break the inner loop and process next vertex
                break 
            
            # If current ancestor has no slots, move up to its parent
            curr = parent.get(curr, 0) # Use .get again for safety
    
    # The total number of vertices in the maximum possible binary tree is 
    # the root (vertex 1) plus all vertices that were successfully matched with a parent.
    print(matched_count + 1)

# Call the main solver function
solve()
0