2026 杭电暑期多校 8-1008-分数越小还是越大越好 · znzryb
# 题目大意
### 分数越小还是越大越好
<!-- Notion block type: heading_4 -->
给定一棵包含 $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$ 中,树的最小可能分数与最大可能分数。
<!-- Notion block type: heading_4 -->
第一行一个整数 $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}$。
<!-- Notion block type: heading_4 -->
对于每组测试数据输出一行两个整数,分别表示树的最小可能分数与最大可能分数。
<!-- Notion block type: heading_4 -->
```
3
3
1 2
2 3
4
1 2
1 3
1 4
5
1 2
1 3
1 4
1 5
```
<!-- Notion block type: heading_4 -->
```
5 7
5 11
6 16
```
<!-- Notion block type: heading_4 -->
**第一组数据**:树是一条链 $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 啊。

```cpp
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代码
::: 源代码
```cpp
```
:::
# 心路历程(WA,TLE,MLE……)