题目内容

在一个树形网络中，有 $n$ 台设备，编号从 1 到 $n$。设备 1 被固定为根设备。设备之间的连接关系构成一棵无环连通树，每台设备可以下挂多台设备；若某台设备没有下挂任何设备，则称其为边缘设备。

现在需要对该网络进行整改。可以选择移除一部分设备，被移除设备的连接随之消失。剩余设备必须形成一棵以设备 1 为根的树；也就是说，如果某台设备被保留，那么它到根设备路径上的所有设备也必须被保留。

整改目标是让剩余网络中所有边缘设备到根设备的距离相等。这里“距离”定义为从根设备到该边缘设备经过的边数。请你计算最少需要移除多少台设备。

约束条件：

• 设备数量 $n$ 不小于 3 且不超过 5000。
• 每条连接的两个端点 $u$ 和 $v$ 均不小于 1 且不超过 $n$，并且 $u \neq v$。
• 输入保证给定的连接关系构成一棵树，共有 $n-1$ 条连接。

输入描述

第一行包含一个整数 $n$，表示网络中的设备总数。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示设备 $u$ 与设备 $v$ 之间存在一条连接。输入仅表示连接关系，不表示父子方向；父子关系需要以设备 1 为根确定。

输出描述

输出一个整数，表示最少需要移除的设备台数，使得剩余网络中所有边缘设备到根设备的距离相等。

样例1

输入

4
1 2
1 3
1 4

输出

0

说明

以设备 1 为根，设备 2、3、4 的深度均为 $1$。所有边缘设备到根设备的距离都是 $1$，已经满足目标条件，因此不需要移除任何设备，最少移除数量为 0。

样例2

输入

5
1 2
2 3
2 4
1 5

输出

1

说明

最优做法是移除设备 5，共移除 1 台。

如图：

样例3

输入

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

输出

3

说明

一种最优做法是移除设备 4、5、8，共移除 3 台。

如图：

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