結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
![]() |
提出日時 | 2023-11-03 23:11:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,407 ms / 2,000 ms |
コード長 | 574 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 90,880 KB |
最終ジャッジ日時 | 2024-09-25 21:24:42 |
合計ジャッジ時間 | 30,787 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
from sys import setrecursionlimitsetrecursionlimit(10**6)n,k = map(int,input().split())adj = [[] for _ in range(n)]for _ in range(n):u,v = map(int,input().split())adj[u-1].append(v-1); adj[v-1].append(u-1)def dfs(v,p):f[v] = True; x[v] = x[p]+1for c in adj[v]:if c==p: continueif f[c]: return x[v]-x[c]+1cnt = dfs(c,v)if cnt: return cntreturn 0f = [False]*n; x = [0]*n; cnt = dfs(0,-1)mod = 998244353; p,q = 0,k*(k-1)%modfor _ in range(cnt-2): p,q = q,((k-1)*p+(k-2)*q)%modprint(q*pow(k-1,n-cnt,mod)%mod)