题目内容

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

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

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

题解

题目描述

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

思路

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