CF219D.Choosing Capital for Treeland
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The country Treeland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are n - 1 roads in the country. We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.
The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city a is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.
Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.
国家 Treeland 由 n 座城市组成,其中某些城市对之间由有向道路连接。全国共有 n−1 条道路。我们已知:若忽略所有道路的方向,则任意两座城市之间均可互相到达(即无向图连通)。
近日,长老会决定为 Treeland 选定首都。首都当然必须是该国的一座城市。长老会将在首都召开会议,并需定期从首都出发前往其他各城市(目前尚未考虑从这些城市返回首都的问题)。因此,若选定城市 a 作为首都,则所有道路的方向必须被调整(必要时可将某些道路反向),使得从城市 a 出发,沿道路方向可以到达其余任意一座城市。
请帮助长老会选出一个首都,使得需要反向的道路数量最少。
输入格式
The first input line contains integer n (2 ≤ n ≤ 2·105) — the number of cities in Treeland. Next n - 1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers s__i, t__i (1 ≤ s__i, t__i ≤ n; s__i ≠ t__i) — the numbers of cities, connected by that road. The i-th road is oriented from city s__i to city t__i. You can consider cities in Treeland indexed from 1 to n.
第一行输入包含一个整数 n(2≤n≤2⋅105)—— 表示树兰国(Treeland)中的城市数量。接下来的 n−1 行每行描述一条道路。每条道路由一对整数 si,ti(1≤si,ti≤n;si=ti)描述,表示该道路所连接的两个城市的编号。第 i 条道路的方向为从城市 si 指向城市 ti。你可以认为树兰国的城市编号为 1 到 n。
输出格式
In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.
第一行输出:若最优地选择首都,需要翻转的最少道路数量。
第二行输出:所有可能的首都选择方式——按升序排列的城市编号序列。
输入输出样例
输入#1
3 2 1 2 3
输出#1
0 2
输入#2
4 1 4 2 4 3 4
输出#2
2 1 2 3
输入解题思路,AI测评打分。不知道怎么写?