CF796D.Police Stations
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Inzane finally found Zane with a lot of money to spare, so they together decided to establish a country of their own.
Ruling a country is not an easy job. Thieves and terrorists are always ready to ruin the country's peace. To fight back, Zane and Inzane have enacted a very effective law: from each city it must be possible to reach a police station by traveling at most d kilometers along the roads.

There are n cities in the country, numbered from 1 to n, connected only by exactly n - 1 roads. All roads are 1 kilometer long. It is initially possible to travel from a city to any other city using these roads. The country also has k police stations located in some cities. In particular, the city's structure satisfies the requirement enforced by the previously mentioned law. Also note that there can be multiple police stations in one city.
However, Zane feels like having as many as n - 1 roads is unnecessary. The country is having financial issues, so it wants to minimize the road maintenance cost by shutting down as many roads as possible.
Help Zane find the maximum number of roads that can be shut down without breaking the law. Also, help him determine such roads.
因赞终于找到了身怀巨款的赞恩,于是他们共同决定建立一个属于自己的国家。
治理一个国家并非易事。小偷与恐怖分子时刻准备着破坏国家的和平。为应对这一威胁,赞恩与因赞颁布了一项极为有效的法律:从任意一座城市出发,必须能够在至多 d 千米的路程内(沿道路行驶)抵达一座警察局。

该国共有 n 座城市,编号为 1 到 n,仅由恰好 n − 1 条道路连接。所有道路长度均为 1 千米。初始状态下,任意两座城市之间均可通过这些道路相互到达。该国还设有 k 座警察局,分别位于某些城市中。特别地,当前的城市结构已满足上述法律所要求的条件。另外请注意:同一座城市中可能设有多个警察局。
然而,因赞认为保留多达 n − 1 条道路实属冗余。由于国家正面临财政困难,它希望尽可能多地关闭道路,以最小化道路维护成本。
请帮助因赞找出在不违反法律的前提下,最多可关闭的道路数量;并进一步确定应关闭哪些道路。
输入格式
The first line contains three integers n, k, and d (2 ≤ n ≤ 3·105, 1 ≤ k ≤ 3·105, 0 ≤ d ≤ n - 1) — the number of cities, the number of police stations, and the distance limitation in kilometers, respectively.
The second line contains k integers _p_1, _p_2, ..., p__k (1 ≤ p__i ≤ n) — each denoting the city each police station is located in.
The i-th of the following n - 1 lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — the cities directly connected by the road with index i.
It is guaranteed that it is possible to travel from one city to any other city using only the roads. Also, it is possible from any city to reach a police station within d kilometers.
第一行包含三个整数 n、k 和 d(2 ≤ n ≤ 3⋅105,1 ≤ k ≤ 3⋅105,0 ≤ d ≤ n − 1),分别表示城市的数量、警察局的数量以及以千米为单位的距离限制。
第二行包含 k 个整数 p1,p2,...,pk(1 ≤ pi ≤ n),每个数表示一个警察局所在的城市编号。
接下来的 n − 1 行中,第 i 行包含两个整数 ui 和 vi(1 ≤ ui,vi ≤ n,ui = vi),表示由第 i 条道路直接相连的两座城市。
保证仅通过这些道路可以从任意一座城市到达其他任意一座城市。此外,保证从任意一座城市出发,均能在 d 千米范围内到达至少一个警察局。
输出格式
In the first line, print one integer s that denotes the maximum number of roads that can be shut down.
In the second line, print s distinct integers, the indices of such roads, in any order.
If there are multiple answers, print any of them.
第一行,输出一个整数 s,表示最多可以关闭的道路数量。
第二行,输出 s 个互不相同的整数,即这些道路的编号(顺序任意)。
若存在多个答案,输出任意一个即可。
输入输出样例
输入#1
6 2 4 1 6 1 2 2 3 3 4 4 5 5 6
输出#1
1 5
输入#2
6 3 2 1 5 6 1 2 1 3 1 4 1 5 5 6
输出#2
2 4 5
说明/提示
In the first sample, if you shut down road 5, all cities can still reach a police station within k = 4 kilometers.
In the second sample, although this is the only largest valid set of roads that can be shut down, you can print either 4 5 or 5 4 in the second line.
在第一个样例中,若关闭道路 5,则所有城市仍能在 k = 4 千米范围内到达一个警察局。
在第二个样例中,尽管这是唯一一组可关闭的最大有效道路集合,但在第二行中,你可输出 4 5 或 5 4 中的任意一种。
输入解题思路,AI测评打分。不知道怎么写?