8670: Expected Inversions

For an integer sequence a1,...,an of length n, its inversion number $\mathrm{inv}(a)$ is defined as the number of integer pairs $(i,j)$ such that $1\le i<j\le n$ and ai>aj.

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 du. We call (d1,d2,...,dn) 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 QP with $P,Q$ being integers and 

$Q！\equiv 0(\mathrm{mod}998244353)$. There is exactly one integer $R\in [0,998244353)$ that satisfies $QR\equiv P(\mathrm{mod}998244353)$. Print this R as the answer.

The first line of input contains a single integer $1\le T\le 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≤n≤105), indicating the number of vertices in the tree. Each of the next n-1 lines contains two integers $(1\le u,v\le n)$, indicating an edge on the tree. It is guaranteed that the input edges form a tree.

1
3
1 2
1 3

499122177
1
2