CF1830D Mex Tree(数据范围微改)

题目描述

给定一棵有 $n$ 个节点的树。对于每个节点，你可以将其染成 $0$ 或 $1$。

一条路径 $(u,v)$ 的价值等于从 $u$ 到 $v$ 的最短路径上所有节点的颜色的 MEX $^\dagger$。

一次染色的价值等于所有满足 $1 \leq u \leq v \leq n$ 的路径 $(u,v)$ 的价值之和。

请问该树的任意染色方案中，最大可能的价值是多少？

$^\dagger$ MEX（minimum excluded）是指一个数组中最小的不属于该数组的非负整数。例如：

• $[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 \leq t \leq 10$），表示测试用例的数量。

每组测试用例的第一行为一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示树的节点数。

接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n, a_i \neq b_i$），表示在节点 $a_i$ 和 $b_i$ 之间有一条边。保证给定的边构成一棵树。

输出格式

对于每组测试用例，输出该树的任意染色方案中可能取得的最大价值。

输入输出样例 #1

输入 #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

说明/提示

在第一个样例中，我们可以将节点 $2$ 染成 $1$，节点 $1,3$ 染成 $0$。此时，所有路径的价值如下：

• $(1,1)$ 的价值为 $1$
• $(1,2)$ 的价值为 $2$
• $(1,3)$ 的价值为 $2$
• $(2,2)$ 的价值为 $0$
• $(2,3)$ 的价值为 $2$
• $(3,3)$ 的价值为 $1$

可以发现所有路径的价值之和为 $8$，这是最大可能的值。

由 ChatGPT 4.1 翻译