結果
問題 |
No.1424 Ultrapalindrome
|
ユーザー |
|
提出日時 | 2022-02-24 20:49:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 1,309 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 92,692 KB |
最終ジャッジ日時 | 2024-07-02 13:42:01 |
合計ジャッジ時間 | 4,753 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
from collections import deque n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): u, v = map(int, input().split()) u -= 1 v -= 1 edges[u].append(v) edges[v].append(u) cnt = 0 for i in range(n): if len(edges[i]) == 1: s = i cnt += 1 if cnt == 2: print("Yes") exit() queue = deque() queue.append((s, -1)) dist = [-1] * n dist[s] = 0 bef = [-1] * n while queue: pos, bpos = queue.popleft() for npos in edges[pos]: if npos == bpos: continue elif dist[npos] != -1: continue dist[npos] = dist[pos] + 1 bef[npos] = pos queue.append((npos, pos)) if dist[pos] % 2 == 1: print("No") exit() d = dist[pos] // 2 for _ in range(d): pos = bef[pos] queue = deque() queue.append((pos, -1)) dist = [-1] * n dist[pos] = 0 while queue: pos, bpos = queue.popleft() cnt = 0 for npos in edges[pos]: if npos == bpos: continue elif dist[npos] != -1: continue cnt += 1 dist[npos] = dist[pos] + 1 queue.append((npos, pos)) if bpos != -1 and cnt > 1: print("No") exit() for i in range(n): if len(edges[i]) == 1 and dist[i] != d: print("No") exit() print("Yes")