A7218 | $雾港城的神秘区域$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城的道路网是一棵树：共有 $n$ 个路口，$n-1$ 条双向道路，任意两路口之间都恰好存在一条简单路径。 城里有若干路口安装了“信标”（被标记的点）。统领准备封闭一些道路，把整座城市分成若干个互不连通的辖区。 为了避免信号互相干扰，要求 每个辖区内的信标数量不超过 $1$ 。 请你计算：至少需要封闭多少条道路，才能满足要求。

第一行两个整数 $n,k$，表示路口数与信标数。 第二行 $k$ 个两两不同的整数，表示装有信标的路口编号（若 $k=0$，该行为空行）。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条连接 $u$ 与 $v$ 的道路。

输出一个整数，表示最少需要封闭的道路条数。

输入 #1

输出 #1

样例解释 解释：信标在 $2,5,7$。如果封闭道路 $3-5$ 与 $5-7$， 则三个信标分别落在三个不同的辖区里（每块至多一个信标），因此答案不超过 $2$； 而 $3$ 个信标至少需要 $3$ 个辖区，删边一次只能让辖区数加 $1$，所以至少删 $2$ 条。 因此输出为 $2$。 数据范围与测试点 * $1\le n\le200000$ * $0\le k\le n$ * 输入保证给出的是一棵树，且信标位置两两不同。 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出