問題一覧 > 通常問題

No.2531 Coloring Vertices on Namori

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 92
作問者 : 👑 AngrySadEight / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10237 / 自分の提出
問題文最終更新日: 2023-10-24 15:34:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 411 オムニバスコンテスト (順位表) の他の問題:

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $N$ edges. The $i$-th edge connects vertex $u_i$ and vertex $v_i$ bidirectionally.

You paint each vertex of this graph with $1$ color chosen from the $K$ colors $1, 2, \dots, K$. However, adjacent vertices cannot be painted the same color.

Find the total number of ways to paint the vertices, modulo $998244353$.

Two ways of painting the vertices are considered different if there exists a vertex that is painted a different color.

Constraints

  • All input values are integers.
  • $3 \leq N \leq 2 \times 10^5$
  • $2 \leq K \leq 2 \times 10^5$
  • $1 \leq u_i < v_i \leq N$
  • $(u_i, v_i) \neq (u_j, v_j) (i \neq j)$
  • The given graph is simple and connected.

Input

The input is given from standard input in the following format.

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_N$ $v_N$

Output

Print the total number of ways to paint the vertices, modulo $998244353$.

Sample

Sample 1
Input
3 3
1 2
2 3
1 3
Output
6

Let $c_1, c_2, c_3$ be the colors painted on vertices $1, 2, 3$. The following $6$ ways satisfy the condition.

  • $(c_1, c_2, c_3) = (1, 2, 3)$
  • $(c_1, c_2, c_3) = (1, 3, 2)$
  • $(c_1, c_2, c_3) = (2, 1, 3)$
  • $(c_1, c_2, c_3) = (2, 3, 1)$
  • $(c_1, c_2, c_3) = (3, 1, 2)$
  • $(c_1, c_2, c_3) = (3, 2, 1)$

Sample 2
Input
4 2
1 2
2 3
3 4
1 4
Output
2

Let $c_1, c_2, c_3, c_4$ be the colors painted on vertices $1, 2, 3, 4$. The following $2$ ways satisfy the condition.

  • $(c_1, c_2, c_3, c_4) = (1, 2, 1, 2)$
  • $(c_1, c_2, c_3, c_4) = (2, 1, 2, 1)$

Sample 3
Input
10 200000
1 2
1 3
2 4
2 5
3 9
4 7
5 8
1 10
6 10
7 10
Output
956138134

Print the total number of ways to paint the vertices, modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。