Skip to content

11611: 【原1611】迟来的13

题目

题目描述

author: Chika 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1611 ## Description

我有一个奇怪的想法。

我现在有一棵树,每个点初始都涂成了白色。

只有一个我指定的点例外,它是蜜柑色的。

现在我想把整棵树都变成蜜柑色,但是我得一步一步来。

每一步,我都会选择一个到最近蜜柑色节点尽量远的一个白色节点,然后把它染成蜜柑色。

但这样可能有多个符合要求的点,我只会染编号最小的那一个。

在整棵树都变成了蜜柑色之后,我想知道我染色的顺序是什么。

奇怪的想法总是会带来愉快的心情,于是我将会随机生成这棵树哦♪

Input Format

第一行是一个数n,表示这棵树的节点个数。

接下来n-1行,每行读入两个整数u, v,来描述树上的一条边。

最后是一个数x,表示我初始选定的点。

Output Format

输出n-1行,第i行输出我第i步染色的点的编号。

Sample Input

5
1 2
1 3
2 4
2 5
3

Sample Output

4
5
1
2

Limits

  • 对于60%的数据,n <= 1000
  • 对于100%的数据,n <= 100000

保证整棵树随机生成。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!