#P0069. 世界树上找米库
世界树上找米库
题目描述
给定一棵有 个地点的无根树,地点编号为 ,每条边的长度均为 。
恰好连接一条边的地点称为 Sekai 点。对每个非 Sekai 点 ,定义 为它到最近 Sekai 点的距离,距离等于路径上的边数。
在所有非 Sekai 点中, 取得最大值的地点称为 Miku 点。请找出全部 Miku 点,并按编号从小到大输出。
输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 ,代表数据组数,每组测试数据描述如下:
第一行输入一个整数 。
此后 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向边。保证这些边构成一棵树。
保证单个测试文件内所有数据组的 之和不超过 。
输出格式
对于每组测试数据,输出两行。
第一行输出 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 解释
第一组为链 ,叶子 是 Sekai 点,地点 到最近叶子的距离都为 ,因此两点都需输出。
第二组中,地点 到最近叶子 或 的距离为 ,其余非叶子到最近叶子的距离均为 ,因此只输出 。
1
5
1 2
1 3
1 4
1 5
1
1