結果
問題 |
No.2531 Coloring Vertices on Namori
|
ユーザー |
![]() |
提出日時 | 2023-11-04 18:21:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 461 ms / 2,000 ms |
コード長 | 726 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 150,844 KB |
最終ジャッジ日時 | 2024-09-25 22:12:49 |
合計ジャッジ時間 | 11,998 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
n,k=map(int,input().split()) M=998244353 e=[[] for i in range(n)] d=[0]*n for i in range(n): a,b=map(int,input().split()) a-=1 b-=1 e[a]+=[b] e[b]+=[a] d[a]+=1 d[b]+=1 q1=[0,0] q2=[0,k] for i in range(2,n+2): q1+=[(q1[i-1]*(k-2)+q2[i-1]*(k-1))%M] q2+=[q1[i-1]] if 1 not in d: print(q2[n+1]) exit() for i in range(n): if d[i]==1: S=i break v=[0]*n v[S]=1 q=[S] g=[0]*n f=0 while len(q)>0: s=q[-1] while g[s]<len(e[s]): t=e[s][g[s]] if v[t]>0 and t!=q[-2]: l=v[s]+1-v[t] f=1 break if v[t]==0: break g[s]+=1 if f: break if g[s]<len(e[s]): g[s]+=1 v[t]=v[s]+1 q+=[t] else: v[s]=0 q.pop() print(q2[l+1]*pow(k-1,n-l,M)%M)