题目描述

我是小蝶，我遇到了无数个我，虽然她们一点儿也不吵闹，但我还是带着她们去寻找我的朋友们，我必须弄明白这一切。

在云中城，我找到了我的朋友云宝，她是一匹帅气的天马，和我一点儿也不一样。遗憾的是，云宝也遇到了一个问题，她告诉我：

组织 WHU(World Horse Unite) 经常在新闻中传播一些消息，但是很遗憾，有些消息经过一段时间的传播后，被证实是一个假消息，为了挽回颜面，WHU 不得不重新散播一个消息进行辟谣。

“但是她们总是让我去辟谣”，云宝大声说，“可是我有点弄不清楚。”

整理了一下云宝的描述，简便起见，我认为消息在一棵 $n$ 个点和 $n - 1$ 条边的无向无权树上传播。

WHU 散播的假消息自时间 $0$ 开始从节点 $r$ 开始开始传播，每个单位时间消息会扩散至相邻的点。形式化的，在时间 $t$ 时，所有距离 $r$ 不超过 $t$ 的节点均接收到了这个消息，即点集 $V(r,t)=\{v|\text{dis}(r,v) \leq t\}$，其中 $\text{dis}(u,v)$ 表示树上两点 $u$ 和 $v$ 间的唯一简单路径的边数。

在时间 $t_0$ 开始时，WHU 会委托云宝选择一个新的节点 $r'$ 进行辟谣，每个单位时间辟谣会扩张至距离当前节点距离不超过 $k$ 的节点上，即辟谣的速度是假消息的 $k$ 倍。形式化的，在时间 $t$（$t \geq t_0$）时，所有距离 $r'$ 不超过 $k(t - t_0)$ 的节点接收到了辟谣，即点集 $V'(r',t)=\{v|\text{dis}(r',v) \leq k(t - t_0)\}$。

现在 $r$ 和 $t_0$ 都是确定的，但是云宝并不确定需要选择从哪里开始辟谣，也不确定用多快的速度辟谣，因此，我需要对所有满足 $1 \leq k < n$ 的 $k$ 回答，任取 $r'$ 时，假消息最早什么时候能全部被辟谣。形式化的，找到一个最早的时间点 $t$，满足辟谣所覆盖的点完全包含了假消息所覆盖的点即 $V(r,t) \subseteq V'(r',t)$。

输入格式

第一行一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示树的点数。

接下来 $n - 1$ 行，每行两个整数 $u,v$，表示树上的一条边。

接下来一行两个整数 $r$（$1 \leq r \leq n$），$t_0$（$1 \leq t_0 \leq n$），表示上述题意中的参数。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示当 $k = i$ 时，上述询问的最早时间的值。

5
1 2
2 3
3 4
4 5
1 2

4 3 3 3 3

解释 #1

辟谣比假消息晚两个单位时间，假消息在 $t = 4$ 时将会覆盖全部的点。当 $k = 1$ 时，仅能选取 $r' = 3$，最早 $t = 4$ 时完成覆盖；当 $k = 2$ 时，可以选取 $r' = 2,3$，$t = 3$ 时，假消息覆盖了点 $\{1,2,3,4\}$，辟谣分别覆盖了点 $\{1,2,3,4\}$ 和 $\{1,2,3,4,5\}$，均满足完全覆盖；当 $k = 3$ 时，可以选取 $r' = 2,3,4$，$t = 3$ 时，所有点都被辟谣覆盖；当 $k = 4$ 时，任取 $r'$，总能时间 $3$ 时所有点都被覆盖。

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

4 2 2 2 2 2 2 2

解释 #2

对于 $k = 1,2 \dots ,n$，一种可行的 $r'$ 选取为 $1,2, \dots ,2$。