1011. 奶龙和噜噜的糖豆

题目描述

奶龙和噜噜来到了一棵神奇的树前。树根处有一颗会随机移动的糖豆，而树上的叶子藏着两人的终点旗帜。

奶龙先选择一个叶子插上黄色旗帜，噜噜看见奶龙的选择后，再选择另一个叶子插上蓝色旗帜。随后糖豆从根节点出发，在树上随机游走。

奶龙希望糖豆先到达自己的旗帜，噜噜则会尽力阻止它。

给定一棵包含 $n$ 个节点的无根树。节点编号为 $1,2,\ldots,n$，并将节点 $1$ 视为根。

一个节点称为叶子，当且仅当它在以 $1$ 为根的树中没有儿子。

游戏过程如下：

1. 奶龙先选择一个叶子 $a$。
2. 噜噜知道 $a$ 后，选择另一个叶子 $b\ne a$。
3. 一颗糖豆从节点 $1$ 出发。
4. 若糖豆当前位于既不是 $a$ 也不是 $b$ 的节点 $u$，它会在所有与 $u$ 相邻的节点中等概率选择一个，并移动到该节点。
5. 糖豆第一次到达 $a$ 或 $b$ 时，游戏立即结束。若先到达 $a$，则奶龙获胜；若先到达 $b$，则噜噜获胜。

奶龙希望最大化自己的获胜概率，噜噜希望最小化奶龙的获胜概率，且双方都采用最优策略。

求奶龙最终的获胜概率。

可以证明，该概率是一个有理数。设答案为 $\frac pq$，其中 $q\not\equiv0\pmod{998244353}$，你需要输出

$p\cdot q^{-1}\pmod{998244353},$

其中 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的乘法逆元。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示树的节点数。
• 接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树上有一条连接 $u$ 和 $v$ 的无向边。

$1\le T \le 20,$

$3\le n\le 5200,$

$\sum n\le 5200.$

保证输入是一棵树，并且以节点 $1$ 为根时至少有两个叶子。

输出格式

对于每组测试数据，输出一行一个整数，表示双方均采用最优策略时，奶龙获胜概率在模 998244353 意义下的值。

样例输入

2
3
1 2
1 3
7
1 2
1 7
2 3
2 6
3 4
3 5

样例输出

499122177
665496236

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1011