A104746.雾港城的神秘区域

入门

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

雾港城的道路网是一棵树:共有 nn 个路口,n1n-1 条双向道路,任意两路口之间都恰好存在一条简单路径。
城里有若干路口安装了“信标”(被标记的点)。统领准备封闭一些道路,把整座城市分成若干个互不连通的辖区。

为了避免信号互相干扰,要求 每个辖区内的信标数量不超过 11
请你计算:至少需要封闭多少条道路,才能满足要求。

输入格式

第一行两个整数 n,kn,k,表示路口数与信标数。
第二行 kk 个两两不同的整数,表示装有信标的路口编号(若 k=0k=0,该行为空行)。
接下来 n1n-1 行,每行两个整数 u,vu,v,表示一条连接 uuvv 的道路。

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    2

说明/提示

样例解释

解释:信标在 2,5,72,5,7。如果封闭道路 353-5575-7
则三个信标分别落在三个不同的辖区里(每块至多一个信标),因此答案不超过 22
33 个信标至少需要 33 个辖区,删边一次只能让辖区数加 11,所以至少删 22 条。
因此输出为 22

数据范围与测试点

  • 1n2000001\le n\le200000
  • 0kn0\le k\le n
  • 输入保证给出的是一棵树,且信标位置两两不同。
测试点编号 nn 上界
141\sim4 n20n\le20
5105\sim10 n10000n\le10000
112011\sim20 n200000n\le200000
首页