← 返回题目列表

Codeforces · 1830/D

D. 墨西哥树

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

给你一棵有 $$$n$$$ 个节点的树。对于每个节点,您可以将其着色为 $$$0$$$ 或 $$$1$$$。

路径 $$$(u,v)$$$ 的值等于 $$$u$$$ 和 $$$v$$$ 之间最短路径的节点颜色的 MEX$$$^\dagger$$$。

着色值等于所有路径 $$$(u,v)$$$ 的值之和,使得 $$$1 \leq u \leq v \leq n$$$。

树的任何颜色的最大可能值是多少?

$$$^{\dagger}$$$ 数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:

- $$$[2,2,1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3,1,0,1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0,3,1,2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树中的节点数。

每个测试用例的以下 $$$n-1$$$ 行包含 $$$2$$$ 整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) - 表示顶点 $$$a_i$$$ 和 $$$a_i$$$ 之间的边$$$b_i$$$。保证给定的边形成一棵树。

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

输出

对于每个测试用例,打印树的任何颜色的最大可能值。

示例

输入 #1

4
3
1 2
2 3
4
1 2
1 3
1 4
10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10
1

输出 #1

8
15
96
1

注意

在第一个示例中,我们将为 $$$1$$$ 中的顶点 $$$2$$$ 和 $$$0$$$ 中的顶点 $$$1,3$$$ 着色。之后,我们考虑所有路径:

- $$$(1,1)$$$ 价值 $$$1$$$
- $$$(1,2)$$$ 价值 $$$2$$$
- $$$(1,3)$$$ 价值 $$$2$$$
- $$$(2,2)$$$ 价值 $$$0$$$
- $$$(2,3)$$$ 价值 $$$2$$$
- $$$(3,3)$$$ 价值 $$$1$$$

我们注意到值的总和是 $$$8$$$,这是可能的最大值。