/ CWOI / 题库 /

2017.07.15 P2 大灾变!!!!!!!!

2017.07.15 P2 大灾变!!!!!!!!

注:此题数据过于玄学,不要去认真地算复杂度,因为肯定能跑过。。。

时间就是金钱,我的朋友!

题目描述

死亡之翼降临了!艾泽拉斯大陆的子民们必须逃出他的魔爪!
艾泽拉斯的结构是一棵树,这棵树上的一些节点是地精建造的通往地下避难所的洞口。
除了这些洞口之外,树上的每个节点上都有一个种族,每个种族通过树上的一条边都需要一个单位时间。
因为地精比较矮小,所以洞口很窄,每个单位时间只能让一个种族通过,但是一个单位时间内的一个节点上可以存在多个种族。
地精们需要你求出最少需要多少单位时间才能让所有种族躲进地下避难所。

输入格式

第 1 行两个整数 n 和 m 表示节点个数和洞口个数;
接下来 n - 1 行每行两个整数表示树上的每一条边;
第 n + 1 行 m 个整数表示所有洞口的编号。

输出格式

一个整数 t 表示让所有种族躲进地下避难所的最少时间。

样例输入

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

样例输出

3

数据范围

对于 100%的数据,n <= 2000, m <= 40。

限制

3s

来源

CWOI新高二专题测试十三

信息

难度
4
分类
图结构 | 网络流二分查找 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者