AT_agc066_e [AGC066E] Sliding Puzzle On Tree

[problemUrl]: https://atcoder.jp/contests/agc066/tasks/agc066_e 頂点に $ 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 $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられます． > $ 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\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 $ 以下である． ### Sample Explanation 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 $ の場合について，次の図も参考にしてください． !\[\](https://img.atcoder.jp/agc066/f2dc57ae01aa4f1ccb51c1a2b8fe7d15.png) ### Sample Explanation 2 それぞれのテストケースで与えられている木は次の図の通りです： !\[\](https://img.atcoder.jp/agc066/744a8d907603331334518cc5d7b62bb9.png)