#P0069. 世界树上找米库

世界树上找米库

题目描述

\hspace{15pt}给定一棵有 nn 个地点的无根树,地点编号为 1∼n1\sim n,每条边的长度均为 11。

\hspace{15pt}恰好连接一条边的地点称为 Sekai 点。对每个非 Sekai 点 vv,定义 d(v)d(v) 为它到最近 Sekai 点的距离,距离等于路径上的边数。

\hspace{15pt}在所有非 Sekai 点中,d(v)d(v) 取得最大值的地点称为 Miku 点。请找出全部 Miku 点,并按编号从小到大输出。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦104)t\left(1\leqq t\leqq10^4\right),代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n(3≦n≦2×105)n\left(3\leqq n\leqq2\times10^5\right)。

\hspace{15pt}此后 n−1n-1 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向边。保证这些边构成一棵树。

\hspace{15pt}保证单个测试文件内所有数据组的 nn 之和不超过 2×1052\times10^5。

输出格式

\hspace{15pt}对于每组测试数据,输出两行。

\hspace{15pt}第一行输出 Miku 点的数量;第二行按编号从小到大输出所有 Miku 点,相邻编号以空格分隔。

测试样例

2
4
1 2
2 3
3 4
10
2 1
3 2
4 3
5 4
6 3
7 5
8 7
9 5
10 2
2
2 3
1
4

样例 1 解释

\hspace{15pt}第一组为链 1↔2↔3↔41\leftrightarrow2\leftrightarrow3\leftrightarrow4,叶子 1,41,4 是 Sekai 点,地点 2,32,3 到最近叶子的距离都为 11,因此两点都需输出。

图片

\hspace{15pt}第二组中,地点 44 到最近叶子 66 或 99 的距离为 22,其余非叶子到最近叶子的距离均为 11,因此只输出 44。

1
5
1 2
1 3
1 4
1 5
1
1