E - Sliding Puzzle On Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

頂点に 1 から N の番号が付いた N 頂点の木が与えられます．木の i 番目の辺は頂点 u_i と頂点 v_i を結んでいます．

K=1, 2, \ldots, N に対して次の問題を解いてください：

1, 2, \ldots, K の番号のついた K 個の石があり，番号 i の石は頂点 i に置かれています． 次の操作を繰り返し行うことができます：

  • 木の辺で接続された 2 頂点 u, v であって，u に石が置かれていて，v には石が置かれていないものを選ぶ．u に置かれている石を v に移動させる．

操作後の石の配置としてありうる個数を 998244353 で割った余りを求めてください．ただし，2 つの石の配置はある番号の石が置かれている頂点が異なる場合に区別します．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1\leq T\leq 10^5
  • 1\leq N\leq 2\times 10^5
  • 1\leq u_i, v_i\leq N
  • 与えられるグラフは木である．
  • 1 個の入力に含まれるテストケースについて，それらの N の総和は 2\times 10^5 以下である．

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

出力

T 行出力してください．i 行目には i 番目のテストケースについて，K=1, 2, \ldots, N に対する答えを半角スペース区切りで出力してください．

入力例 1

1
4
1 2
1 3
1 4

出力例 1

4 12 4 1

石の配置を番号 1, 2, \ldots, K の石が置かれている頂点の番号の列により表すと，

  • K=1 の場合，ありうる石の配置は (1), (2), (3), (4) の 4 個です．
  • K=2 の場合，ありうる石の配置は (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3) の 12 個です．
  • K=3 の場合，ありうる石の配置は (1,2,3), (4,1,3), (4,2,1), (4,2,3) の 4 個です．
  • K=4 の場合，ありうる石の配置は (1,2,3,4) の 1 個です．

K=3 の場合について，次の図も参考にしてください．

入力例 2

4
1
5
1 4
5 2
3 4
2 1
7
1 7
2 7
5 6
4 1
1 6
3 6
10
1 2
2 3
3 4
4 5
5 6
2 7
3 8
4 9
5 10

出力例 2

1
5 10 10 5 1
7 42 210 840 84 7 1
10 90 720 5040 30240 151200 604800 720 10 1

それぞれのテストケースで与えられている木は次の図の通りです：

Score: 1500 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge of the tree connects vertices u_i and v_i.

For each K=1, 2, \ldots, N, solve the following problem:

There are K stones numbered 1, 2, \ldots, K, with the stone numbered i placed on vertex i. You can repeatedly perform the following operation:

  • Choose two vertices u and v connected by an edge such that u has a stone on it and v does not. Move the stone from u to v.

Find the number, modulo 998244353, of possible configurations of the stones after performing the operations. Two configurations are distinguished if and only if there is a stone whose position differs between those configurations.

T test cases are given; solve each of them.

Constraints

  • 1\leq T\leq 10^5
  • 1\leq N\leq 2\times 10^5
  • 1\leq u_i, v_i\leq N
  • The given graph is a tree.
  • The sum of N over all test cases in a single input is at most 2\times 10^5.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

Output

Print T lines. The i-th line should contain the answers for K=1, 2, \ldots, N for the i-th test case, separated by spaces.

Sample Input 1

1
4
1 2
1 3
1 4

Sample Output 1

4 12 4 1

Let us represent the configuration of stones by the sequence of vertices where the stones numbered 1, 2, \ldots, K are placed.

  • For K=1, there are 4 possible configurations: (1), (2), (3), (4).
  • For K=2, there are 12 possible configurations: (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3).
  • For K=3, there are 4 possible configurations: (1,2,3), (4,1,3), (4,2,1), (4,2,3).
  • For K=4, there is 1 possible configuration: (1,2,3,4).

For K=3, refer to the following figure.

Sample Input 2

4
1
5
1 4
5 2
3 4
2 1
7
1 7
2 7
5 6
4 1
1 6
3 6
10
1 2
2 3
3 4
4 5
5 6
2 7
3 8
4 9
5 10

Sample Output 2

1
5 10 10 5 1
7 42 210 840 84 7 1
10 90 720 5040 30240 151200 604800 720 10 1

The tree given in each test case is as follows: