题解

题目描述

给定一棵以节点 $1$ 为根的树型网络，包含 $n$ 台设备（节点编号 $1$ 到 $n$）。网络中任意两节点通过边相连，最后没有子节点的称为“边缘设备”。希望移除尽可能少的节点，使得剩下网络中所有边缘设备到根设备的距离都相同。输出最少需要移除的节点数。

思路

1. 先从根节点 $1$ 做一次 BFS/DFS，计算每个节点到根的初始距离 $depth[v]$。
2. 设定一个目标距离 $H$，希望所有保留后的边缘节点深度都为 $H$。
3. 对于每个节点 $v$，定义状态

题目内容

在一个树形的网络拓扑中，有 $n$ 台设备，编号 $1$ 到 $n$ ，其中我们固定 $1$ 为根设备，如上图：根设备下可下挂多台设备(如设备编号 $2、3$ )，以此类推每一台设备下都可能下挂1台或者多台设备，最后没有下挂设备的设备成为边缘设备(如设备 $3、5、6、7$ )。

现在我们希望对网络进行整改，将组网中的部分设备移除，使得所有的边缘设备到根设备的距离相同，请你计算下最少需要移除多少台设备。

如上图：我们只需要移除 $3$ 号和 $5$ 号设备,可以使得剩下的所有边缘设备( $6、7$ )到根设备的距离相同。

注：整个网络是单个连通的树型组网且没有环

输入描述

用例第一行为一个整数 $n(3≤n≤5000)$ ，代表网络设备数目。

接下来 $n-1$ 行每行包含两个整数 $u,v(1≤ u,v≤n,u≠v)$ ，代表设备 $u$ 与设备 $v$ 相连接(注意仅代表链接关系，不表明确父子关系)。

注：我们保证每个设备的编号都小于等于 $n$ ，且不重复；$n$ 个网络设备，必然有 $n-1$ 条连接。

输出描述

输出最少移除多少台设备，可以使得剩下的所有边缘设备到根设备距离都相同。

样例1

输入

7
1 2
1 3
2 4
2 5
4 6
4 7

输出

2

说明

如题目实例图中：我们移除 $3$ 号和 $5$ 号 $2$ 台设备，可以使得剩下的所有边缘设备（$6/7$）到根设备的距离相同。

样例2

输入

5
4 1
2 4
5 1
5 3

输出

0

说明

该用例中的树形图为如下，可见不需要移除任何设备就满足边缘设备（2和3）到根设备1的距离都相等。

样例3

输入

7
1 2
2 3
3 4
1 5
1 6
1 7

输出

2

说明

该用例移除设备 $4$ 后，再移除设备 $3$ 即可。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写