P14812 [CCPC 2024 Harbin Site] A Game On Tree

There is a tree (a connected undirected graph with $n$ nodes and $n-1$ edges) consisting of $n$ nodes, with nodes numbered from $1$ to $n$. Clearly, there is a unique simple path between any two nodes in the tree. Xiaohong and Xiaolan are playing a game on this tree. In each game, both players $\textbf{independently and uniformly}$ select a random simple path from all $\frac{n(n-1)}{2}$ simple paths (regardless of direction) that exist in the tree. Note that they may choose the same path. Let $X$ denote the number of edges that are common to both selected paths, and the score of the game is $X^2$. Your task is to find the expected value of the score $E(X^2)$ when Xiaohong and Xiaolan play the game once, and output the result modulo $998244353$ (see the output format for details).

The first line contains a positive integer $T$ ($1\le T \le 10^4$), representing the number of test cases. For each test case, the first line contains a positive integer $n$ ($2\le n \le 10^5$), representing the number of nodes in the tree. The next $n-1$ lines each contain two positive integers $u, v$ ($1\le u,v \le n$), indicating that there is an edge between nodes $u$ and $v$. The input is guaranteed to be a tree. The sum of all $n$ over all test cases does not exceed $10^6$.

For each test case, output a single integer, representing the answer modulo $998244353$. Formally, let $M=998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac p q$, where $p$ and $q$ are integers and $q \not\equiv 0\pmod M$. Output the integer equal to $p\cdot q^{-1}\pmod M$, where $q^{-1}$ denotes the modular multiplicative inverse of $q$ modulo $M$. In other words, output such an integer $x$ that $0\le x < M$ and $x\cdot q\equiv p\pmod M$. It can be proved that there is exactly one $x$ which meets the condition.

For the first test case in the example, the answer without taking the modulo is $\frac{10}{9}$. Among the $9$ possible cases: - In $2$ cases, the number of common edges between the two paths is $0$; - In $6$ cases, the number of common edges between the two paths is $1$; - In $1$ case, the number of common edges between the two paths is $2$. Therefore, the answer is $E(X^2) = \frac{2 \cdot 0^2 + 6 \cdot 1^2 + 1 \cdot 2^2}{9} = \frac{10}{9}$.