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^4$），表示测试用例的数量。 每组测试用例的第一行为一个整数 $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$ 之间有一条边。保证给定的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个样例中，我们可以将节点 $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 翻译