ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 R: 警察局
内存限制:256 MB
时间限制:2 S
题面:传统
评测方式:文本比较
上传者:
提交:4
通过:3
返回比赛
提交
提交记录
题目描述
Inzane终于找到了Zane,他有很多钱,所以他们一起决定建立一个属于自己的国家。
统治一个国家并非易事。
小偷和恐怖分子总是准备破坏国家的和平。
为了反击,赞恩和因赞恩制定了一项非常有效的法律:从每个城市出发,沿着道路最多行驶d公里就可以到达警察局。
全国共有n个城市,编号从1到n,仅通过n-1条道路相连。所有道路都有1公里长。
最初可以使用这些道路从一个城市前往任何其他城市。
该国还在一些城市设有k个警察局。特别是,该市的结构符合上述法律的要求。还要注意,一个城市可能有多个警察局。
然而,赞恩觉得拥有多达n-1条道路是不必要的。
该国正面临财政问题,因此它希望通过关闭尽可能多的道路来降低道路维护成本。
帮助Zane找到可以在不违反法律的情况下关闭的道路的最大数量。
此外,帮助他确定此类道路。
输入格式
第一行包含3个整数n,k,d(2 ≤ n ≤ 3·10
5
, 1 ≤ k ≤ 3·10
5
, 0 ≤ d ≤ n - 1),分别表示城市数量、警察局数量和距离限制(以公里为单位)。
第二行包含k个整数p
i
(1<=p
i
<=n),每个表示每个警察局所在的城市。
以下n-1行中的第i行包含两个整数u
i
和v
i
(1 ≤ u
i
, v
i
≤ n, u
i
≠ v
i
) ,表示u
i
和v
i
存在双向道路。
保证仅使用道路就可以从一个城市前往其他任何城市。此外,从任何城市都可以在d公里内到达警察局。
输出格式
在第一行中,打印一个整数s,表示可以关闭的道路的最大数量。
在第二行中,按任意顺序打印s个不同的整数,即这些道路的索引。
如果有多个答案,请打印其中任何一个。
输入样例
复制
6 3 2 1 5 6 1 2 1 3 1 4 1 5 5 6
输出样例
复制
2 4 5
数据范围与提示
样例输入
6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
样例输出
1
3
分类标签
cf796D
2100
constructive
algorithms
dfs
and
similar
dp
graphs
shortest
paths
trees