#1084216 (PyPy3) No.1153 ねこちゃんゲーム

• 問題: No.1153 ねこちゃんゲーム
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:25:41
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 7,695 bytes
• コンパイル時間: 208 ms
• コンパイル使用メモリ: 82,284 KB
• 実行使用メモリ: 351,924 KB
• 最終ジャッジ日時: 2025-05-14 13:26:40
• 合計ジャッジ時間: 10,273 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 5 TLE * 1 -- * 34

ソースコード

import sys

sys.setrecursionlimit(4 * 10**5) 

# Global-like variables to store context for a single root's computation
_current_adj = None
_current_memo_for_root = None # Memoization for (curr, prev) states for the current root
_current_tin_for_root = None  # tin values for DFS tree from the current root
_current_tout_for_root = None # tout values for DFS tree from the current root
_current_dfs_time_counter = 0 # Time counter for DFS

def dfs_tin_tout_builder(u, p):
    global _current_dfs_time_counter, _current_tin_for_root, _current_tout_for_root, _current_adj
    _current_dfs_time_counter += 1
    _current_tin_for_root[u] = _current_dfs_time_counter
    
    for v_neighbor in _current_adj[u]:
        if v_neighbor == p:
            continue
        dfs_tin_tout_builder(v_neighbor, u)
    
    _current_dfs_time_counter += 1
    _current_tout_for_root[u] = _current_dfs_time_counter

def is_ancestor(u_potential_ancestor, v_node):
    global _current_tin_for_root, _current_tout_for_root
    # Check if u_potential_ancestor is an ancestor of v_node (or u_potential_ancestor == v_node)
    # This check is valid only within the context of the current DFS tree (defined by _current_tin_for_root, _current_tout_for_root)
    if u_potential_ancestor == 0: # Dummy node is not an ancestor of any real node
        return False
    if u_potential_ancestor not in _current_tin_for_root or v_node not in _current_tin_for_root:
        # This might happen if nodes are not reachable from the current root (not an issue for a connected tree)
        return False 
    return _current_tin_for_root[u_potential_ancestor] <= _current_tin_for_root[v_node] and \
           _current_tout_for_root[u_potential_ancestor] >= _current_tout_for_root[v_node]

def calculate_grundy_for_state(curr_u, prev_p):
    # fixed_root context is implicit via global _current_tin_for_root etc.
    global _current_adj, _current_memo_for_root
    
    state_key = (curr_u, prev_p)
    if state_key in _current_memo_for_root:
        return _current_memo_for_root[state_key]

    reachable_next_states_grundies = set()
    for neighbor_v in _current_adj[curr_u]:
        if neighbor_v == prev_p: # Cannot immediately go back to where it came from
            continue

        # Check if neighbor_v is on the historical path from fixed_root to prev_p.
        # The path taken so far is: fixed_root -> ... -> prev_p -> curr_u.
        # The new node neighbor_v must not be in {fixed_root, ..., prev_p}.
        # This is equivalent to: neighbor_v is not an ancestor of prev_p (inclusive) in the DFS tree from fixed_root.
        # (prev_p == 0 is special: curr_u is fixed_root, history is just {fixed_root}.
        #  neighbor_v is forbidden only if neighbor_v == fixed_root, but neighbor_v != curr_u.)
        
        is_forbidden_by_history = False
        if prev_p != 0: # If prev_p is not the dummy node
            if is_ancestor(neighbor_v, prev_p): 
                is_forbidden_by_history = True
        
        if not is_forbidden_by_history:
            reachable_next_states_grundies.add(calculate_grundy_for_state(neighbor_v, curr_u))
    
    g_val = 0
    while g_val in reachable_next_states_grundies:
        g_val += 1
    
    _current_memo_for_root[state_key] = g_val
    return g_val

def solve():
    global _current_adj, _current_memo_for_root, _current_tin_for_root, _current_tout_for_root, _current_dfs_time_counter

    N, M = map(int, sys.stdin.readline().split())
    # A_starts contains the 1-indexed starting nodes for cats 0 to M-1
    A_starts = list(map(int, sys.stdin.readline().split())) 
    
    _current_adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v_node = map(int, sys.stdin.readline().split())
        _current_adj[u].append(v_node)
        _current_adj[v_node].append(u)

    if N == 1: # Single node tree
        print("-1 -1") # No moves possible
        return

    # Store computed Grundy values for G(start_node, dummy_prev_node)
    # Key: start_node, Value: Grundy value
    # Also cache tin/tout maps to avoid recomputing DFS if same root is processed again.
    grundy_values_for_each_distinct_start_node = {}
    tin_maps_cache = {}
    tout_maps_cache = {}

    distinct_start_nodes = sorted(list(set(A_starts)))

    for s_node in distinct_start_nodes:
        _current_dfs_time_counter = 0
        _current_tin_for_root = {}
        _current_tout_for_root = {}
        _current_memo_for_root = {} # Fresh memo for this root
        
        dfs_tin_tout_builder(s_node, 0) # 0 is a dummy parent for the root s_node
        
        # Cache tin/tout for potential reuse when finding the winning move
        tin_maps_cache[s_node] = dict(_current_tin_for_root)
        tout_maps_cache[s_node] = dict(_current_tout_for_root)

        # Calculate Grundy value for starting at s_node (previous node is dummy 0)
        g_val = calculate_grundy_for_state(s_node, 0)
        grundy_values_for_each_distinct_start_node[s_node] = g_val

    # Calculate XOR sum of all cats' initial Grundy values
    total_grundy_xor_sum = 0
    # cat_initial_grundies[i] stores G-value for i-th cat (0-indexed)
    cat_initial_grundies = [0] * M 
    for i in range(M):
        cat_i_start_node = A_starts[i]
        g_val = grundy_values_for_each_distinct_start_node[cat_i_start_node]
        cat_initial_grundies[i] = g_val
        total_grundy_xor_sum ^= g_val
        
    if total_grundy_xor_sum == 0:
        print("-1 -1") # Kiri-chan wins
    else:
        # Ebi-chan wins. Find a winning move.
        # Iterate through each cat. If moving cat k makes its Grundy value G_k',
        # then we need G_k' == total_grundy_xor_sum ^ G_k_initial.
        found_winning_move = False
        for cat_list_idx in range(M): # cat_list_idx is 0 to M-1
            cat_actual_id = cat_list_idx + 1 # Problem uses 1-indexed cat IDs
            
            current_cat_origin_node = A_starts[cat_list_idx]
            current_cat_initial_g_val = cat_initial_grundies[cat_list_idx]

            target_g_val_for_next_state = total_grundy_xor_sum ^ current_cat_initial_g_val
            
            # Set up context for this cat's origin_node
            _current_tin_for_root = tin_maps_cache[current_cat_origin_node]
            _current_tout_for_root = tout_maps_cache[current_cat_origin_node]
            _current_memo_for_root = {} # Fresh memo for this calculation phase, or could reuse if states are truly identical

            # Iterate over possible first moves for this cat
            # Current state for this cat: (current_cat_origin_node, dummy_prev_0)
            # A move is to neighbor_v.
            # The state after move: (neighbor_v, current_cat_origin_node as prev_p)
            for neighbor_v_of_origin in _current_adj[current_cat_origin_node]:
                # The history for this move is {current_cat_origin_node, neighbor_v_of_origin}.
                # The call is calculate_grundy_for_state(neighbor_v_of_origin, current_cat_origin_node)
                # fixed_root for this game is current_cat_origin_node.
                
                g_val_of_state_after_move = calculate_grundy_for_state(neighbor_v_of_origin, current_cat_origin_node)

                if g_val_of_state_after_move == target_g_val_for_next_state:
                    print(f"{cat_actual_id} {neighbor_v_of_origin}")
                    found_winning_move = True
                    break 
            if found_winning_move:
                break
        
        # According to Sprague-Grundy theorem, a winning move must exist.
        # If not found, it indicates a bug in implementation or understanding.
        # assert found_winning_move 

solve()