New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2176: 关闭道路

内存限制：512 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计

题目描述

你正在管理一个由单向道路组成的城市交通网络。
人们按照顺序从同一城市出发，每个人在开始移动前会等待前一个人停止移动。
人们遵循以下原则直至目的地：查看当前城市的所有出口道路，选择通向标签最小城市的道路。
当一个人到达目的地或者无出口道路的城市时会停止移动。
如果某人无法到达目的地，则后续的人将离开。
在每个人进入交通网络之前，你可以永久关闭任意数量的道路，以确保他们到达目的地。
你选择关闭的道路将对后续的人将不可用。
目前有 n 个城市，编号从 1 到 n，n - 1 条有向道路，每条道路从编号较小的城市指向编号较大的城市。
因此该网络将形成以城市 1 为根的树。
现在有 m 个人从城市 1 按顺序出发，第 i 个人目的地为城市 d[i]。
如果你执行最优策略，最多能保证多少人到达目的地。

输入格式

第一行为正整数 n 和 m，2≤n,m≤200000。
接下来 n-1 行，每行两个数字 u,v，表示从 u 到 v 存在道路，1≤u＜v≤n。
接下来 m 行，每行一个整数表示 d[i]，2≤d[i]≤n。

输出格式

输出一个整数表示答案。

输入样例 复制 

样例1：
8 5
1 2
4 8
4 6
1 4
2 5
4 7
2 3
5
2
6
4
8

样例2：
4 4
1 2
1 3
1 4
3
2
3
4

输出样例 复制 

样例1：
5

样例2：
1

数据范围与提示

来源：2023 PACNW