問題一覧 > 通常問題

No.1614 Majority Painting on Tree

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : 👑 ygussanyygussany / テスター : ngtkanangtkana tatyamtatyam
3 ProblemId : 5951 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-23 08:41:39

問題文

T.T. 君は木が好きで,木の各辺に色を塗って遊ぼうとしています. ただし,T.T. 君は多数決も好きなので,以下の条件をすべて満たすように色を塗りたいと考えています.

  • 各辺はちょうど $1$ 種類の色で塗られている.
  • 各色は少なくとも $1$ 本の辺に塗られている.
  • 各頂点について,自身に接続する辺のうち過半数(半分よりも真に多く)に塗られている色が存在するならば,その頂点に接続する辺はすべて同じ色で塗られている.

$N$ 頂点の木と使う色の種類数 $C$ が与えられるので,そのような色の塗り方が何通りあるかを求めてください. ただし,色は互いに区別でき,$2$ つの色の塗り方に関して,それぞれで塗られた色が異なるような辺が存在するときに,それらの塗り方を異なるものと見なします. また,答えは非常に大きくなることがあるので,素数 $998244353$ で割った余りを出力してください.

入力

$N$ $C$
$A_1\ \ B_1$
$A_2\ \ B_2$
   $\vdots$
$A_{N-1}\ \ B_{N-1}$

  • $2 \le N \le 10^5$
  • $1 \le C \le 256$
  • $1 \le A_i, B_i \le N \ \ (1 \le i \le N - 1)$
  • 入力は全て整数である.
  • 与えられるグラフはである.
  • 頂点には $1, 2, \dots, N$ の番号が付いている.
  • 辺には $1, 2, \dots, N - 1$ の番号が付いている.
  • 辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結ぶ.

出力

条件を満たすような色の塗り方の総数を $998244353$ で割った余りを出力してください.

サンプル

サンプル 1
入力
5 2
1 2
1 3
1 4
1 5
出力
6

頂点 $1$ に接続する $4$ 本の辺に関して,$2$ 本ずつに異なる色を塗る場合にすべての条件を満たします. 色 $1$ を塗る辺の選び方が $\binom{4}{2} = 6$ 通りなので,答えは $6$ 通りとなります.

すべての辺に同じ色を塗ると $2$ つ目の条件を満たせず,$2$ 色をそれぞれ $1$ 本と $3$ 本に塗ると $3$ つ目の条件を満たせません.

サンプル 2
入力
5 2
1 2
3 2
3 4
5 4
出力
14

各頂点に接続する辺が $2$ 本以下なので,どのように塗っても $3$ つ目の条件を満たします. 色を $1$ 種類しか使わない(すべての辺に同じ色を塗る)場合を除いて,答えは $2^4 - 2 = 14$ 通りです.

サンプル 3
入力
7 4
1 2
1 3
1 4
2 5
2 6
2 7
出力
816

サンプル 4
入力
7 256
1 2
1 3
1 4
2 5
2 6
2 7
出力
0

すべての色を使うことは不可能です.

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