結果

問題 No.1295 木と駒
ユーザー qwewe
提出日時 2025-05-14 13:21:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,443 bytes
コンパイル時間 372 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 260,268 KB
最終ジャッジ日時 2025-05-14 13:23:58
合計ジャッジ時間 5,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 6 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N = int(sys.stdin.readline())
    if N == 0: # Handle empty case if necessary, though constraints say N >= 2
        return
    if N == 1: # Only one node, always visited
        sys.stdout.write("Yes\n")
        return

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

    adj = [[] for _ in range(N)]
    for u_raw, v_raw in edges_raw:
        u, v = u_raw - 1, v_raw - 1 # 0-indexed
        adj[u].append(v)
        adj[v].append(u)

    adj_sorted = [sorted(neighbors) for neighbors in adj]

    output_results = []

    for start_node_initial_idx in range(N): # 0-indexed start_node_idx
        current_node = start_node_initial_idx
        visited_nodes = {start_node_initial_idx}
        
        type2_chain_path_nodes = set()
        possible_to_visit_all = True 

        while len(visited_nodes) < N:
            made_type1_move = False
            best_next_node_type1 = -1
            
            for neighbor in adj_sorted[current_node]:
                if neighbor not in visited_nodes:
                    best_next_node_type1 = neighbor
                    break 
            
            if best_next_node_type1 != -1:
                current_node = best_next_node_type1
                visited_nodes.add(current_node)
                type2_chain_path_nodes.clear() 
                made_type1_move = True
            
            if made_type1_move:
                continue

            if current_node in type2_chain_path_nodes:
                possible_to_visit_all = False
                break 
            type2_chain_path_nodes.add(current_node)

            made_type2_move = False
            best_next_node_type2 = -1
            for neighbor in adj_sorted[current_node]:
                if neighbor in visited_nodes: 
                    best_next_node_type2 = neighbor
                    break
            
            if best_next_node_type2 != -1:
                current_node = best_next_node_type2
                made_type2_move = True

            if made_type2_move:
                continue

            possible_to_visit_all = False
            break 

        if len(visited_nodes) == N and possible_to_visit_all:
            output_results.append("Yes")
        else:
            output_results.append("No")

    for res in output_results:
        sys.stdout.write(res + "\n")

solve()
0