2026 杭电暑期多校 8-1008-分数越小还是越大越好

题目大意

分数越小还是越大越好

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

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

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

对于两个顶点 $u,v$，设它们之间简单路径上的顶点集合为 $V(u,v)$（当 $u=v$ 时 $V(u,v)=\{u\}$），定义

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

树的分数定义为

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

求在所有标签排列 $P$ 中，树的最小可能分数与最大可能分数。

第一行一个整数 $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\times 10^{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

第一组数据：树是一条链 $1-2-3$，需要把 $\{0,1,2\}$ 分配给三个顶点。

取 $P=(0,2,1)$，即 $P_1=0,\;P_2=2,\;P_3=1$：

$(u,v)$	路径上的标签集合	$f(u,v)$
$(1,1)$	$\{0\}$	$1$
$(1,2)$	$\{0,2\}$	$1$
$(1,3)$	$\{0,2,1\}$	$3$
$(2,2)$	$\{2\}$	$0$
$(2,3)$	$\{2,1\}$	$0$
$(3,3)$	$\{1\}$	$0$

总和为 $5$，这是该树能取到的最小分数。

取 $P=(1,0,2)$：

$(u,v)$	路径上的标签集合	$f(u,v)$
$(1,1)$	$\{1\}$	$0$
$(1,2)$	$\{1,0\}$	$2$
$(1,3)$	$\{1,0,2\}$	$3$
$(2,2)$	$\{0\}$	$1$
$(2,3)$	$\{0,2\}$	$1$
$(3,3)$	$\{2\}$	$0$

总和为 $7$，这是该树能取到的最大分数。

第二组数据：树是以顶点 $1$ 为中心、含 $3$ 片叶子的菊花图，枚举全部 $4!=24$ 种标签排列可知分数的取值范围为 $[5,11]$。

第三组数据：树是以顶点 $1$ 为中心、含 $4$ 片叶子的菊花图，枚举全部 $5!=120$ 种标签排列可知分数的取值范围为 $[6,16]$。

思路讲解

最小化的情况比较简单：

是链的话，那么就是 $2*N-1$。

不是链的话就是 N+1 啊。

cin >> N;
vector<vector<int> > g(N + 2);
for (int i = 1; i <= N - 1; ++i) {
	ll u, v;
	cin >> u >> v;
	g[u].push_back(v);
	g[v].push_back(u);
}
ll leaf_ct = 0;
for (int i = 1; i <= N; ++i) {
	if (SZ(g[i]) == 1) {
		leaf_ct++;
	}
}
if (leaf_ct <= 2) {
	// 一条链的情况
	cout << 2 * N - 1 << " ";
} else {
	cout << N + 1 << " ";
}

求解最大值

状态定义
设 $DP(u, v)$ 表示：将标签 $0, 1, \dots, \operatorname{dist}(u, v)$ 分配给路径 $u \dots v$ 上的所有节点，所能获得的最大累计贡献分数。

那么这个DP状态是如何定义出来的？我们在近期训练题目一句话总结里面写了。

AC代码

源代码

心路历程（WA，TLE，MLE……）