結果

問題 No.1424 Ultrapalindrome
ユーザー LyricalMaestro
提出日時 2025-09-07 02:26:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,738 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 100,692 KB
最終ジャッジ日時 2025-09-07 02:26:46
合計ジャッジ時間 7,589 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/415

from collections import deque

def calc_dist(N, next_nodes, start):
    # 直径をもとめる
    queue = deque()
    dists = [float("inf") for _ in range(N)]
    prevs = [-1 for _ in range(N)]
    queue.append(start)
    dists[start] = 0

    while len(queue) > 0:
        v = queue.popleft()
        for w in next_nodes[v]:
            if dists[w] == float("inf"):
                dists[w] = dists[v] + 1
                prevs[w] = v
                queue.append(w)
    
    return dists, prevs



def main():
    N = int(input())
    next_nodes = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        next_nodes[a - 1].append(b - 1)
        next_nodes[b - 1].append(a - 1)
    
    dists, _ = calc_dist(N, next_nodes, 0)
    ans_i = -1
    max_d = -1
    for i in range(N):
        if max_d < dists[i]:
            max_d = dists[i]
            ans_i = i
    dists, prevs = calc_dist(N, next_nodes, ans_i)

    D = max(dists)
    if D % 2 != 0:
        print("No")
        return
    
    target_i = -1
    for i in range(N):
        if D == dists[i]:    
            target_i = i
            break

    d = D // 2
    v = target_i
    path = []
    while v != ans_i:
        path.append(v)
        v = prevs[v]
    path.reverse()
    x = path[d - 1]

    dists, prevs = calc_dist(N, next_nodes, x)

    for i in range(N):
        if len(next_nodes[i]) == 1:
            if dists[i] != d:
                print("No")
                return
        else:
            if i != x:
                if len(next_nodes[i]) != 2:
                    print("No")
                    return


    print("Yes")












if __name__ == "__main__":
    main()
0