#P3059. 「DTOI-5」3-1

「DTOI-5」3-1

题目背景

——『太阳』这种东西,以前似乎是存在的。

传说是这么讲的——白色的火焰发出闪耀的光芒,天空则是清澄无比的蔚蓝。

据说诸神与其创造物所掀起的『大战』,使得大地化为焦土,灰烬遮蔽了苍穹。

灰烬冲击到天上流动的星辰之力——精灵回廊,发出了光芒,将天空染成红色。

而那样的红色,覆盖了仍然持续着互相残杀的每一块土地。

或者那是这个星球本身发出的悲鸣与流出的鲜血吧……

血色的天空上,只有——蓝色的灰飘然落下。

回来吧3579,我最骄傲的信仰/ll

题目描述

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

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

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

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

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

输入格式

第一行,一个整数 nn

接下来 n1n - 1 行,每行两个整数 ui,viu_i, v_i

输出格式

nn 行,第 ii 行一个整数表示 k=ik = i 的答案。

5
1 2
1 3
2 4
2 5
0
1
2
4
6
见下发的 hope/hope2.in
见下发的 hope/hope2.ans

提示

【样例解释 1\bm 1

  • k=1k = 1 时,里克只需要呆在装置 11 处。
  • k=2k = 2 时,里克的路径可以是 1211 \rightarrow 2 \Rightarrow 1
  • k=3k = 3 时,里克的路径可以是 12411 \rightarrow 2 \rightarrow 4 \Rightarrow 1
  • k=4k = 4 时,里克的路径可以是 1241311 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3\rightarrow 1
  • k=5k = 5 时,里克的路径可以是 131252411 \rightarrow 3\rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1

【样例解释 2\bm 2

这组数据满足测试点编号 132013 \sim 20 的性质。

【数据规模与约定】

测试点编号 特殊限制
121 \sim 2 n=3n = 3
343 \sim 4 n=5n = 5
565 \sim 6 n=100n = 100
787 \sim 8 n=1000n = 1000
9109 \sim 10 ui=1,vi=i+1u_i = 1, v_i = i + 1
111211 \sim 12 ui=i,vi=i+1u_i = i, v_i = i + 1
132013 \sim 20 无特殊限制

对于所有数据,1n1051 \leq n \leq 10^51ui,vin1 \leq u_i, v_i \leq n