1008. 分数越小还是越大越好

题目描述

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\ldots,N$。

你需要选择一个 $0$ 到 $N-1$ 的排列 $P$，并将 $P_i$ 作为顶点 $i$ 的标签。

对于一个整数集合 $S$，定义 $\operatorname{MEX}(S)$ 为没有出现在 $S$ 中的最小非负整数。

对于两个顶点 $u,v$，设它们之间简单路径上的顶点集合为 $V(u,v)$，定义

$f(u,v)=\operatorname{MEX}({P_x\mid x\in V(u,v)})$。

树的分数定义为

$\operatorname{score}(P)=\sum_{u=1}^{N}\sum_{v=u}^{N}f(u,v)$。

求所有标签排列中，树的最小可能分数和最大可能分数。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据的格式如下：

第一行输入一个整数 $N$，表示树的顶点数。

接下来 $N-1$ 行，每行输入两个整数 $u,v$，表示树中存在一条连接顶点 $u$ 和顶点 $v$ 的无向边。

对于一组测试数据：

$3\le N\le 2000$；

$1\le u,v\le N$；

输入保证给出的边构成一棵树。

OJ 中只有一个正式测试点，该测试点满足：

$T=1000$；

$\sum N^2=2\times10^7$。

输出格式

对于每组测试数据输出一行两个整数，分别表示树的最小可能分数和最大可能分数。

样例输入

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

样例输出

5 7
5 11
6 16

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1008