题目描述

题目描述

小 H 在玩一款游戏。

这是一款对城市进行建设的游戏，游戏里有 $n$ 个城市。

为了使城市之间能够通信，小 H 用 $n-1$ 条边连接了城市。对于一条边 $(x,y)$，它保证了城市 $x$ 和城市 $y$ 能直接通信。通过这些边，任意两个城市能够直接或间接通信。

不难发现，上述做法存在一些问题。对于两座城市，如果它们之间需要经过的中转站越多，那么每次发送信息所需要的时间就越长。这就导致一些城市通信便利，一些城市通信不便利。

然而，增加边的数量会导致小 H 无法管理而出现问题。为了解决这个矛盾，小 H 想出了一个办法，每经过一段固定的时间，就重新随机的构建一次网络。这样一来，任意两个城市通信时间的期望值都是相等的。

然而，重构网络也是需要代价的。假设原网络为 $T_1$，新网络为 $T_2$，假设两个网络有 $x$ 条边是一样的，那么小 H 在调整时就可以忽略这些边。

自然，能忽略的边越多越好，因此小 H 认为这种方案的的价值为 $x\cdot 2^x$。

现在，小H将进行第一次网络重构，请问，所有方案的价值之和为多少？

当然，这个答案比较大，所有你只需要求其对 $998244353$ 取模的值。

形式化题目

给定树 $T_1=\{V,E_1\},|V|=n$，假设点集 $V$ 能构成的生成树集合为 $S$，你需要求：

$$\left(\sum_{T_2\in S} |E_1\cap E_2|\cdot 2^{|E_1∩E_2 |}\right) \bmod 998244353 $$

不难发现，$|S|=n^{n-2}$。

输入格式

第一行一个整数 $n$ 。

接下来 $n-1$ 行，每行两个整数 $x_i,y_i$ ，描述 $T_1$ 上的一条边。

输出格式

输出一行，表示价值之和对 $998244353$ 取模的结果。

4
1 2
2 3
3 4

94

数据范围与提示

本题采用捆绑测试。

对于所有数据，满足 $1 \le n \le 2\times 10^6$ 。

子任务见下表：

子任务编号	$n$	特殊性质	分值
$1$	$\le 80$	无	$5$
$2$	$\le 300$		$5$
$3$	$\le 3000$	特殊性质 A	$5$
$4$		特殊性质 B	$5$
$5$		无	$10$
$6$	$\le 10^5$	特殊性质 A	$10$
$7$		特殊性质 B	$10$
$8$	$\le 2\times 10^6$	特殊性质 A	$10$
$9$		特殊性质 B	$10$
$10$		无	$30$

表中的特殊性质如下：

• 特殊性质 A：图是一条链。
• 特殊性质 B：图是一张菊花图。

提示

本题 IO 量较大，请使用较快速的读入方法。