← 返回题目列表

Codeforces · 2101/F

F. 徐粉碎阳光

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

给你一棵有 $$$n$$$ 个顶点的树,其中每个顶点可以是红色、蓝色或白色。的 凉爽 被定义为红色和蓝色顶点之间的最大距离$$$^{\text{*}}$$$。

形式上,如果我们将第 $$$i$$$ 个顶点的颜色表示为 $$$c_i$$$,则在所有顶点对 $$$1\le u, v\le n$$$ 上,颜色的冷度为 $$$\max d(u, v)$$$,其中 $$$c_u$$$ 为 红色 和 $$$c_v$$$ 是 蓝色。如果没有红色或蓝色顶点,则冷度为零。

你的任务是计算树的所有 $$$3^n$$$ 可能颜色的酷度总和,以 $$$998\,244\,353$$$ 为模。

$$$^{\text{*}}$$$树中两个顶点$$$a$$$和$$$b$$$之间的距离等于顶点$$$a$$$和顶点$$$b$$$之间唯一简单路径上的边数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 3000$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行均包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u, v\le n$$$) - 树边缘的端点。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出树的所有 $$$3^n$$$ 可能颜色的酷度总和,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

3
3
1 2
2 3
6
1 2
1 3
1 4
3 5
5 6
17
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
3 10
7 11
7 12
11 13
13 14
14 15
10 16
16 17

输出
复制

18
1920
78555509

注意

在第一个测试用例中,有 $$$12$$$ 颜色至少有一个蓝色和一个红色节点。下面的图片展示了它们的色彩和酷感:

所有这些颜色都很酷$$$2$$$
所有这些颜色都很酷$$$1$$$

因此,所有可能颜色的酷度总和为 $$$6\cdot 2 + 6\cdot 1 = 18$$$。

在第二个测试用例中,以下是一些冷度为 $$$3$$$ 的着色示例: