結果

問題 No.1424 Ultrapalindrome
ユーザー lam6er
提出日時 2025-03-26 15:50:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 1,585 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 101,572 KB
最終ジャッジ日時 2025-03-26 15:51:02
合計ジャッジ時間 5,404 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from collections import deque
def main():
    N = int(sys.stdin.readline().strip())
    edges = [[] for _ in range(N + 1)]
    degrees = [0] * (N + 1)
    for _ in range(N - 1):
        a, b = map(int, sys.stdin.readline().split())
        edges[a].append(b)
        edges[b].append(a)
        degrees[a] += 1
        degrees[b] += 1
    leaves = [i for i in range(1, N + 1) if degrees[i] == 1]
    k = len(leaves)
    if k <= 2:
        print("Yes")
        return
    high_degree_nodes = [i for i in range(1, N + 1) if degrees[i] >= 3]
    if len(high_degree_nodes) != 1:
        print("No")
        return
    center = high_degree_nodes[0]
    # BFS to compute distances and parents
    dist = [-1] * (N + 1)
    parent = [0] * (N + 1)
    q = deque([center])
    dist[center] = 0
    while q:
        u = q.popleft()
        for v in edges[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    # Check all leaves have the same distance from center
    d = dist[leaves[0]]
    for leaf in leaves:
        if dist[leaf] != d:
            print("No")
            return
    # Check all nodes in path from leaf to center (except leaf and center) have degree 2
    for leaf in leaves:
        current = leaf
        while current != center:
            current_parent = parent[current]
            if current != leaf and degrees[current] != 2:
                print("No")
                return
            current = current_parent
    print("Yes")
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0