I am Fluttershy, and I've encountered countless versions of myself. Even though they are not noisy at all, I still take them with me to search for my friends. I must figure this out.
In Cloudsdale, I found my friend, Rainbow Dash. She is a handsome Pegasus pony, completely different from me. Unfortunately, Rainbow Dash also encountered a problem. She told me:
The organization WHU (World Horse Unite) often spreads some news in the news, but unfortunately, some news, after a period of dissemination, is confirmed to be fake news. In order to save face, WHU has to spread another news to refute it.
"And they always ask me to refute it," Rainbow said loudly, "but I'm a little confused."
After organizing Rainbow's description, for simplicity, I assume that the message is transmitted on a tree with $$$n$$$ nodes and $$$n-1$$$ edges.
The fake news spread by WHU starts from node $$$r$$$ at time $$$0$$$, and spreads to neighboring nodes every unit of time. Formally, at time $$$t$$$, all nodes within distance $$$t$$$ from $$$r$$$ receive this message, that is, the set of nodes $$$V(r,t)=\{v | \mathrm{dis}(r,v)\le t\}$$$, where $$$\mathrm{dis}(u,v)$$$ denotes the number of edges of the unique simple path between two nodes $$$u$$$ and $$$v$$$ on the tree.
At time $$$t_0$$$, WHU will commission Rainbow to choose a new node $$$r'$$$ to refute the news, and every unit of time, the refutation will spread to nodes within distance no more than $$$k$$$ from the current node, i.e., the rate of refutation is $$$k$$$ times faster than that of fake news. Formally, at time $$$t$$$ ($$$t\ge t_0$$$), all nodes within distance $$$k(t-t_0)$$$ from $$$r'$$$ receive the refutation, that is, the set of nodes $$$V'(r',t)=\{v | \mathrm{dis}(r',v)\le k(t-t_0)\}$$$.
Now $$$r$$$ and $$$t_0$$$ are determined, but Rainbow is not sure where to start refuting, nor how fast to refute. Therefore, I need to answer for all $$$1\le k\le n$$$, when is the earliest time that fake news can be refuted when taking any $$$r'$$$. Formally, find the earliest time $$$t$$$ such that the refutation covers all the nodes covered by the fake news, i.e., $$$V(r,t)\subseteq V'(r',t)$$$.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$), indicating the number of nodes in the tree.
The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$, representing an edge in the tree.
The following line contains two integers $$$r$$$ ($$$1 \leq r \leq n$$$) and $$$t_0$$$ ($$$1 \leq t_0 \leq n$$$), representing the parameters as described above.
A single line containing $$$n$$$ integers, where the $$$i$$$-th integer represents the earliest time value for the above inquiry when $$$k=i$$$.
51 22 33 44 51 2
4 3 3 3 3
81 21 41 53 62 34 77 82 1
4 2 2 2 2 2 2 2
In the first sample, the refutation is two units of time later than the fake news, and the fake news will cover all the nodes at $$$t=4$$$. When $$$k=1$$$, only $$$r'=3$$$ can be chosen to cover all the nodes when $$$t=4$$$; when $$$k=2$$$, $$$r'=2,3$$$ can be chosen, and when $$$t=3$$$, the fake news covers the nodes $$$\{1,2,3,4\}$$$, and the refutation covers the nodes $$$\{1,2,3,4\}$$$ and $$$\{1,2,3,4,5\}$$$, respectively, which satisfy the complete coverage; when $$$k =3$$$, $$$r'=2,3,4$$$ can be chosen, and all nodes are covered by the refutation when $$$t=3$$$; when $$$k=4$$$, any $$$r'$$$, all nodes at time $$$3$$$ are always covered.
In the second example, for $$$k=1,2,\dots,n$$$, a feasible choice for $$$r'$$$ is $$$1,2,\dots,2$$$.
