Choosing Capital for Treeland

ID: 3855

传统题

1000ms

128MiB

难度: 10

上传者:

Description

Treeland国有n个城市，这n个城市连成了一颗树，有n-1条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市i成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为k。你的任务是找到所有满足k最小的首都。

输入包含多个测试点。对于每个测试点，每个测试点的第一行为一个正整数n（2<=n<=2e5）。接下来n-1行，每行两个正整数ai，bi，表示城市a到城市b有一条单向通行的道路。输入以空格分隔，以EOF结尾。

对于每个测试点，第一行输出k，第二行升序输出所有满足条件的首都的编号。

3
2 1
2 3

0
2

树形dp CF DIv2 D