A6284 | Welcome24ever 和神树

Welcome24ever 在视线可及的范围内发现了一颗古老的「神树」。

神树是一颗树，树上有 $n$ 个含有魔法装置的位置。经过初步「考察」，有 $n - 1$ 条魔法连接，第 $i(1 \leq i \leq n - 1)$ 条连接 $u_i, v_i$ 两个魔法装置，保证 $u_i \neq v_i$ 且 $1\leq u_i,v_i\leq n$。这两个装置可以相互双向地在 $1$ 单位时间内通行，保证仅由这 $n - 1$ 条连接，每个魔法装置都可以相互到达。

此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i \in [2, n]$，可以瞬间传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。特殊连接总共只能使用一次。

Welcome24ever 初始在魔法装置 $1$ 处。现在，给出这棵「神树」的结构，Welcome24ever 想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。

Welcome24ever 想让你尽快计算出，对所有 $k \in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，并且随之返回魔法装置 $\bm 1$，最少应花费多少时间。

第一行，一个整数 $n$。

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$。

共 $n$ 行，第 $i$ 行一个整数表示 $k = i$ 的答案。