結果
問題 | No.1424 Ultrapalindrome |
ユーザー |
![]() |
提出日時 | 2021-03-12 21:53:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 430 ms / 2,000 ms |
コード長 | 1,121 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 36,096 KB |
最終ジャッジ日時 | 2024-10-14 16:13:02 |
合計ジャッジ時間 | 7,257 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys input = sys.stdin.readline N=int(input()) E=[[] for i in range(N)] ED=[0]*N for i in range(N-1): x,y=map(int,input().split()) E[x-1].append(y-1) E[y-1].append(x-1) ED[x-1]+=1 ED[y-1]+=1 root=-1 for i in range(N): if ED[i]==1: if root==-1: Q=[i] root=i count=0 for i in range(N): if ED[i]>2: count+=1 if count>=2: print("No") exit() L=[0]*N while Q: x=Q.pop() for to in E[x]: if L[to]==0: L[to]=L[x]+1 Q.append(to) L[root]=0 flag=1 MAX=max(L) for i in range(N): if ED[i]==1: if L[i]==MAX or i==root: True else: print("No") exit() root=L.index(MAX) Q=[root] L2=[0]*N while Q: x=Q.pop() for to in E[x]: if L2[to]==0: L2[to]=L2[x]+1 Q.append(to) L2[root]=0 flag=1 MAX2=max(L2) if MAX!=MAX2: print("No") exit() for i in range(N): if ED[i]==1: if L2[i]==MAX or i==root: True else: print("No") exit() print("Yes")