火车 (train)
【题目描述】
A 国有n 个城市,城市之间有一些双向道路相连,并且城市两两之间有唯一路径。现在有火车在城市 a,需要经过m 个城市。火车按照以下规则行驶:每次行驶到还没有经过的城市中在 m 个城市中最靠前的。现在小 A 想知道火车经过这m 个城市后所经过的道路数量。
【输入数据】
第一行三个整数 n、m、a,表示城市数量、需要经过的城市数量,火车开始时所在位置。
接下来 n-1 行,每行两个整数 x和y,表示 x 和y之间有一条双向道路。
接下来一行 m 个整数,表示需要经过的城市。
【输出数据】
一行一个整数,表示火车经过的道路数量。
【样例输入】
5 4 2
1 2
2 3
3 4
4 5
4 3 1 5
【样例输出】
9
【数据范围】
对于20%的数据:n,m<=1000
对于35%的数据:n<=100000,m<=10000
对于60%的数据:n<=200000,m<=40000
对于100%的数据:N<=500000 ,M<=400000
信息
- ID
- 1049
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 50
- 已通过
- 5
- 通过率
- 10%
- 上传者
相关
在下列比赛中: