log2r种了一棵 n 个节点的树,每个节点都有一颗果实。现在log2r邀请Hikari和Tairitsu摘果子,规则如下:
二人分别选择一个点对 (u,v),定义点对的回忆值为节点u,v的简单路径上的总果实数。
选择之后,log2r会比较两人所选点对的回忆值大小,最终选取回忆值较大点对的那个人会得到它所选取点对简单路径上的所有果实,而另一个人只能遗憾地空手而归。
特别地,若两个点对回忆值相同,由于log2r是光厨,他会把Hikari所选点对相对应的果子分给Hikari。
Hikari和Tairitsu事先并不知道log2r种的树长成什么样子,因此只能随机地从 1~n 中分别选取 u,v 作为点对,请你计算Hikari期望得到多少果实?
题目保证所求期望可以用有理分数P/Q表示,其中P,Q为整数且(P,Q)=1,你需要输出 P.Q−1 mod 998244353 的值。
第一行一个整数n(1≤n≤2×104),代表树的节点数。
接下来n−1行,每行两个整数ai,bi,代表节点编号为ai,bi的点之间存在一条无向边。
一个整数,代表所求答案。
3
1 2
2 3
431340154
6
1 2
1 3
2 4
2 5
3 6
653172233