「DTOI-5」3-1

——『太阳』这种东西，以前似乎是存在的。 传说是这么讲的——白色的火焰发出闪耀的光芒，天空则是清澄无比的蔚蓝。 据说诸神与其创造物所掀起的『大战』，使得大地化为焦土，灰烬遮蔽了苍穹。 灰烬冲击到天上流动的星辰之力——精灵回廊，发出了光芒，将天空染成红色。 而那样的红色，覆盖了仍然持续着互相残杀的每一块土地。 或者那是这个星球本身发出的悲鸣与流出的鲜血吧…… 血色的天空上，只有——蓝色的灰飘然落下。 ~~回来吧3579，我最骄傲的信仰/ll~~

里克在视线可及的范围内发现了一颗古老的「神树」。 神树是一颗树，树上有 $n$ 个含有魔法装置的位置。经过初步「考察」，有 $n - 1$ 条魔法连接，第 $i(1 \leq i \leq n - 1)$ 条连接连接 $1 \leq u_i \neq v_i \leq n$ 两个魔法装置。这两个装置可以相互**双向地**在 $1$ 单位时间内通行，保证仅由这 $n - 1$ 条连接，每个魔法装置都可以相互到达。 此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i \in [2, n]$，可以**瞬间**传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。**特殊连接总共只能使用一次**。 里克初始在魔法装置 $1$ 处。现在，给出这棵「神树」的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。 里克想让你尽快计算出，对所有 $k \in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，**并且随之返回魔法装置 $\bm 1$**，最少应花费多少时间。

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

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

5
1 2
1 3
2 4
2 5

0
1
2
4
6

见下发的 hope/hope2.in

见下发的 hope/hope2.ans

**【样例解释 $\bm 1$】** + $k = 1$ 时，里克只需要呆在装置 $1$ 处。 + $k = 2$ 时，里克的路径可以是 $1 \rightarrow 2 \Rightarrow 1$。 + $k = 3$ 时，里克的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。 + $k = 4$ 时，里克的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3\rightarrow 1$。 + $k = 5$ 时，里克的路径可以是 $1 \rightarrow 3\rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。 **【样例解释 $\bm 2$】** 这组数据满足测试点编号 $13 \sim 20$ 的性质。 **【数据规模与约定】** | 测试点编号 | 特殊限制 | | :--------: | :------: | | $1 \sim 2$ | $n = 3$ | | $3 \sim 4$ | $n = 5$ | | $5 \sim 6$ | $n = 100$ | | $7 \sim 8$ | $n = 1000$ | | $9 \sim 10$ | $u_i = 1, v_i = i + 1$ | | $11 \sim 12$ | $u_i = i, v_i = i + 1$ | | $13 \sim 20$ | 无特殊限制 | 对于所有数据，$1 \leq n \leq 10^5$，$1 \leq u_i, v_i \leq n$。