No.2531 Coloring Vertices on Namori
タグ : / 解いたユーザー数 92
作問者 : 👑
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もしくは右上の雲マークをクリックしてアカウントを作成してください。