結果
問題 | No.1424 Ultrapalindrome |
ユーザー |
![]() |
提出日時 | 2021-03-12 21:56:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 256 ms / 2,000 ms |
コード長 | 1,134 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 81,996 KB |
実行使用メモリ | 125,344 KB |
最終ジャッジ日時 | 2024-10-14 16:14:36 |
合計ジャッジ時間 | 4,699 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys;input = lambda: sys.stdin.readline().rstrip() n = int(input()) Adj = [set() for _ in range(n)] Leaves = set() for i in range(n-1): a, b = map(int,input().split()) a -= 1 b -= 1 Adj[a].add(b) Adj[b].add(a) if a not in Leaves: if len(Adj[a]) == 1: Leaves.add(a) else: Leaves.remove(a) if b not in Leaves: if len(Adj[b]) == 1: Leaves.add(b) else: Leaves.remove(b) n_l = len(Leaves) if n_l == 2: print('Yes') exit() if n%n_l != 1: print('No') exit() ans = 'Yes' Vertices = set(range(n)) while Vertices and n > 2: nxtLeaves = set() Candidates = set() for l in Leaves: Vertices.remove(l) for x in Adj[l]: Candidates.add(x) if len(Adj[x]) == 2: nxtLeaves.add(x) if nxtLeaves == set() and len(Candidates) == 1: break elif len(nxtLeaves) == n_l: for nl in nxtLeaves: Adj[nl] = [a for a in Adj[nl] if a not in Leaves] Leaves = nxtLeaves else: ans = 'No' break n -= len(Leaves) print(ans)