A104746.雾港城的神秘区域
入门
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
雾港城的道路网是一棵树:共有 n 个路口,n−1 条双向道路,任意两路口之间都恰好存在一条简单路径。
城里有若干路口安装了“信标”(被标记的点)。统领准备封闭一些道路,把整座城市分成若干个互不连通的辖区。
为了避免信号互相干扰,要求 每个辖区内的信标数量不超过 1。
请你计算:至少需要封闭多少条道路,才能满足要求。
输入格式
第一行两个整数 n,k,表示路口数与信标数。
第二行 k 个两两不同的整数,表示装有信标的路口编号(若 k=0,该行为空行)。
接下来 n−1 行,每行两个整数 u,v,表示一条连接 u 与 v 的道路。
输出格式
输出一个整数,表示最少需要封闭的道路条数。
输入输出样例
输入#1
7 3 2 5 7 1 2 2 3 3 4 3 5 5 6 5 7
输出#1
2
说明/提示
样例解释
解释:信标在 2,5,7。如果封闭道路 3−5 与 5−7,
则三个信标分别落在三个不同的辖区里(每块至多一个信标),因此答案不超过 2;
而 3 个信标至少需要 3 个辖区,删边一次只能让辖区数加 1,所以至少删 2 条。
因此输出为 2。
数据范围与测试点
- 1≤n≤200000
- 0≤k≤n
- 输入保证给出的是一棵树,且信标位置两两不同。
| 测试点编号 | n 上界 |
|---|---|
| 1∼4 | n≤20 |
| 5∼10 | n≤10000 |
| 11∼20 | n≤200000 |