Expected Inversions

For an integer sequence $a_1,...,a_n$ of length $n$, its inversion number $\mathrm{inv}(a)$ is defined as the number of integer pairs $(i,j)$ such that $1\leq i < j\leq n$ and $a_i > a_j$.

For a given rooted tree of $n$ nodes (with vertices numbered from $1$ to $n$), a **DFS procedure** on the tree is as following.

- During the process, we maintain a **current vertex**, namely $u$, and a **set of visited vertices**, namely $M$.
- Let the root of the tree be $x$. Initially, $u=x$ and $M=\{x\}$.
- Repeat the following process until $M$ contains all vertices:
- - If there is at least one child vertex of $u$ that is not in $M$, randomly choose one among those vertices equiprobably (namely $v$). Set $u$ to $v$ and add $v$ to $M$.
- Otherwise, set $u$ to the father of $u$.

For each $u=1,...,n$, we record the number of vertices in $M$ when $u$ is added to $M$ (including $u$). Let this number be $d_u$. We call $(d_1,d_2,...,d_n)$ a **DFS order**. As **DFS procedure** is non-deterministic, the resulting **DFS order** may vary as well. Assume that each decision in the **DFS procedure** is independent.

You are given an unrooted tree of $n$ vertices, with vertices numbered from $1$ to $n$. For each $i=1,...,n$, compute the expected inversion number of the **DFS order** when rooting the tree at $i$ and start a **DFS procedure**. To avoid precision errors, print the answer modulo $998244353$.

You are given $T$ independent test cases. Solve each of them.

**How to compute non-integers modulo $998244353$:** It can be proved that the answer to this problem can always be written as a fraction $\dfrac{P}{Q}$ with $P,Q$ being integers and $Q\not\equiv 0\pmod{998244353}$. There is exactly one integer $R\in [0,998244353)$ that satisfies $QR\equiv P\pmod{998244353}$. Print this $R$ as the answer.

The first line of input contains a single integer $T(1\leq T\leq 10)$, indicating the number of test cases. Then $T$ test cases follow.

The first line of each test case contains a single integer $n(1\leq n\leq 10^5)$, indicating the number of vertices in the tree. Each of the next $n-1$ lines contains two integers $u,v(1\leq u,v\leq n)$, indicating an edge on the tree. It is guaranteed that the input edges form a tree.

For each test case, print the answers in $n$ lines. The $i$-th line should contain the expected inversion number of the **DFS order** when rooting the tree at vertex $i$.

1
3
1 2
1 3

499122177
1
2

2022“杭电杯”中国大学生算法设计超级联赛（10）