← 返回题目列表

Codeforces · 1929/D

D. 萨沙和城市漫步

中文机器翻译题面 查看原题

萨沙想和他的女朋友在城里散步。该城市由 $$$n$$$ 个交叉路口组成,编号从 $$$1$$$ 到 $$$n$$$。其中一些是通过道路连接的,从任何一个交叉路口,都有一条简单的路径$$$^{\dagger}$$$到任何其他交叉路口。换句话说,交叉路口和交叉路口之间的道路形成一棵树。

一些交叉路口被认为是危险的。由于独自在城市中行走并不安全,萨莎不想在行走过程中经过三个或更多危险的十字路口。

如果满足以下条件,Sasha 称一组交集为良好:

- 如果在城市中只有该集合中包含的交叉路口是危险的,则城市中的任何简单路径包含不超过两个危险交叉路口。

然而,Sasha 不知道哪些十字路口是危险的,因此他对城市中不同的良好十字路口组的数量感兴趣。由于这个数字可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

$$$^{\dagger}$$$简单路径是最多经过每个交叉点一次的路径。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \leq 3 \cdot 10^5$$$) — 城市中交叉路口的数量。

接下来的 $$$(n - 1)$$$ 行描述道路。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — 第 $$$i$$$ 条道路连接的交叉路口的数量。

保证这些道路形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 良好交集的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4
3
1 3
3 2
4
3 4
2 3
3 1
5
1 2
3 4
5 1
2 3
4
1 2
2 3
3 4

输出 #1

7
12
16
11

注意

在第一个测试用例中,有 $$$2^3 = 8$$$ 组交集。除了集合 $$$\{1, 2, 3\}$$$ 之外,所有这些都很好,因为如果交集 $$$1、2$$$ 和 $$$3$$$ 是危险的,那么简单路径 $$$1 - 2 - 3$$$ 包含 $$$3$$$ 危险交集。因此,有 $$$7$$$ 好套装。

在第二个测试用例中,有 $$$2^4 = 16$$$ 组交集。其中,$$$\{1, 2, 3, 4\}$$$、$$$\{1, 2, 3\}$$$、$$$\{1, 3, 4\}$$$、$$$\{2, 3, 4\}$$$ 等集合都不好。因此,总共有 $$$12$$$ 好套装。城市布局如下图所示: