問題一覧 > 通常問題

No.3828 Push, if Possible

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : Rho / テスター : shiomusubi496 ynymxiaolongbao okkuu / テストしたAI : claude-fable-5-1
お気に入りにしたユーザー ProblemId : 14257 / 自分の提出
問題文最終更新日: 2026-11-10 16:05:08
TSG LIVE! 17 プログラミングコンテスト (順位表) の他の問題:

問題文

頂点に $1$ から $N$ の番号がついた木 $T$ があります。 $T$ の $i\ ( 1 \le i \le N-1)$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。 また、それぞれの頂点にはコインが高々 $1$ 枚置かれています。長さ $N$ の文字列 $S$ が与えられ、 $S$ の $i$ 文字目が o の場合頂点 $i$ にはコインが $1$ 枚置かれており、 x の場合頂点 $i$ にコインは置かれていません。

木 $T$ に置かれたコインに対し、以下の手順で操作を行います。

  • $(1,2,\dots, N-1)$ の順列 $(R_1,R_2, \dots, R_{N-1})$ を選ぶ。
  • 変数 $c$ を $0$ で初期化する。
  • $i=1,2,\dots, N-1$ の順に、次の操作を行う。
    • 頂点 $A_{R_i}$ にコインが置かれており頂点 $B_{R_i}$ にコインが置かれていない場合、 頂点 $A_{R_i}$ に置かれているコインを頂点 $B_{R_i}$ に移動させた上で $c$ に $1$ を加算する。 それ以外の場合、何もしない。

$(R_1, R_2, …, R_{N-1})$ としてあり得るものは $(N-1)!$ 通りありますが、それらに対する操作が全て完了した後の $c$ の値の総和を $998244353$ で割った余りを求めてください。

$Q$ 個のテストケースについてこの問題を解いてください。

制約

  • $1 \le Q \le 150$
  • $2 \le N \le 300$
  • $|S|=N$
  • $1 \le A_i, B_i \le N$
  • 与えられるグラフは木
  • $Q$ 個のテストケースにおける $N$ の総和は $300$ 以下
  • $Q, N, A_i, B_i$ は全て整数
  • $S$ は o または x のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

$Q$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_Q$

各テストケースは以下の形式で与えられる。

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

出力

$Q$ 行出力せよ。 $i$ 行目には、 $\mathrm{case}_i$ に対する答えを出力せよ。

サンプル

サンプル1
入力
3
3
oox
1 3
2 3
4
oooo
4 1
4 2
3 1
15
xxooxxxooooxxoo
8 15
5 15
12 9
15 10
11 10
14 13
7 6
9 7
1 6
4 2
2 10
14 7
2 3
13 2
出力
2
0
382344406

$1$ ケース目について、 $(R_1,R_2)$ としてあり得るものは $(1,2)$ と $(2,1)$ です。

  • $(R_1,R_2)=(1,2)$ の場合
    • 辺 $(A_1,B_1)=(1,3)$ について、頂点 $1$ にコインが置かれており頂点 $3$ にはコインは置かれていない。 $c$ を $0$ から $1$ へ更新し、頂点 $1$ のコインを頂点 $3$ へ移動させる。
    • 辺 $(A_2,B_2)=(2,3)$ について、頂点 $2$ と頂点 $3$ の両方にコインが置かれているので何もしない。最終的な $c$ の値は $1$ である。
  • $(R_1,R_2)=(2,1)$ の場合
    • 辺 $(A_2,B_2)=(2,3)$ について、頂点 $2$ にコインが置かれており頂点 $3$ にはコインは置かれていない。 $c$ を $0$ から $1$ へ更新し、頂点 $2$ のコインを頂点 $3$ へ移動させる。
    • 辺 $(A_1,B_1)=(1,3)$ について、頂点 $1$ と頂点 $3$ の両方にコインが置かれているので何もしない。最終的な $c$ の値は $1$ である。

以上より、$1$ ケース目の答えは $2$ になります。

$2$ ケース目について、全ての頂点にコインが置かれているためコインの移動は起こりません。したがって答えは $0$ になります。

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