結果

問題 No.1752 Up-Down Tree
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:21:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,958 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 451,136 KB
最終ジャッジ日時 2025-05-14 13:22:54
合計ジャッジ時間 7,260 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

# Globals for tree structure and memoization
parent = []
children = []
all_descendants_map = [] # Stores strict descendants
memo_dfs = {}

def build_tree_structures(N_nodes, adj_list_unrooted):
    global parent, children, all_descendants_map
    
    parent = [0] * (N_nodes + 1)
    children = [[] for _ in range(N_nodes + 1)]

    # BFS from root 1 to establish parent and children lists
    bfs_q = [(1, 0)] # (node, its_parent_in_bfs_tree)
    parent[1] = 0    # Parent of root 1 is 0 (dummy)
    head = 0
    visited_bfs_nodes = {1}

    while head < len(bfs_q):
        u, p_u = bfs_q[head]
        head += 1
        for v_neighbor in adj_list_unrooted[u]:
            if v_neighbor != p_u: 
                if v_neighbor not in visited_bfs_nodes: # Standard check for tree BFS
                    visited_bfs_nodes.add(v_neighbor)
                    parent[v_neighbor] = u
                    children[u].append(v_neighbor)
                    bfs_q.append((v_neighbor, u))
    
    # Precompute all strict descendants for each node
    all_descendants_map = [set() for _ in range(N_nodes + 1)]
    for i in range(1, N_nodes + 1):
        q_desc_bfs = [] 
        for child_node in children[i]:
            q_desc_bfs.append(child_node)
            all_descendants_map[i].add(child_node)

        head_q_desc = 0
        while head_q_desc < len(q_desc_bfs):
            curr_subtree_node = q_desc_bfs[head_q_desc]
            head_q_desc += 1
            for grandchild_node in children[curr_subtree_node]:
                if grandchild_node not in all_descendants_map[i]:
                    all_descendants_map[i].add(grandchild_node)
                    q_desc_bfs.append(grandchild_node)

def get_strict_ancestors(u_node):
    ancestors = []
    curr = u_node
    p_curr = parent[curr]
    while p_curr != 0: 
        ancestors.append(p_curr)
        curr = p_curr
        p_curr = parent[curr]
    return ancestors

def game_recursion(curr_node, visited_nodes_fset, is_odd_move):
    state = (curr_node, visited_nodes_fset, is_odd_move)
    if state in memo_dfs:
        return memo_dfs[state]

    max_additional_score = 0
    if is_odd_move:
        strict_ancestors = get_strict_ancestors(curr_node)
        for anc in strict_ancestors:
            if anc not in visited_nodes_fset:
                new_visited_fset = visited_nodes_fset | {anc}
                max_additional_score = max(max_additional_score, 1 + game_recursion(anc, new_visited_fset, False))
    else:
        for desc in all_descendants_map[curr_node]:
            if desc not in visited_nodes_fset:
                new_visited_fset = visited_nodes_fset | {desc}
                max_additional_score = max(max_additional_score, 1 + game_recursion(desc, new_visited_fset, True))
    
    memo_dfs[state] = max_additional_score
    return max_additional_score

def main_solve():
    global memo_dfs 

    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        return

    adj_unrooted = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj_unrooted[u].append(v)
        adj_unrooted[v].append(u)

    build_tree_structures(N, adj_unrooted)
    
    max_total_score = 0
    # Any N >= 1 will have at least 1 node, score >= 1.
    # Iterating N start_nodes, minimum score for each is 1. So max_total_score will be at least 1.
    if N > 0:
        max_total_score = 1 # Smallest possible score is 1 (just the starting node)


    for start_node in range(1, N + 1):
        initial_visited_fset = frozenset({start_node})
        current_game_score = 1 + game_recursion(start_node, initial_visited_fset, True)
        if current_game_score > max_total_score:
            max_total_score = current_game_score
            
    print(max_total_score)

if __name__ == '__main__':
    sys.setrecursionlimit(2 * 10**5) # Increased recursion limit for potentially deep paths
    main_solve()
0