魔法传送

题目描述

有一棵树，树上有 \( n \) 个节点，这些节点通过 \( n-1 \) 条边相连，保证树是连通的。每个节点上都有一个魔法装置。每条边的通行时间为 1 单位时间。

除此之外，每个节点（除了根节点）与根节点之间有一个特殊的传送通道，可以瞬间传送到根节点，且传送花费时间为 0。这个特殊传送通道总共只能使用一次。

假设你从树的根节点（节点 1）出发，想要研究尽可能多的魔法装置。每次研究一个魔法装置的时间就是到达该装置的时间，但不需要额外时间。现在，给定这棵树的结构，求对于所有 \( k \in [1, n] \)，如果要恰好研究 \( k \) 个不同的魔法装置并返回到根节点，最少应花费多少时间。

输入格式

• 第一行：一个整数 \( n \)，表示树的节点数。
• 接下来 \( n - 1 \) 行，每行包含两个整数 \( u_i, v_i \)，表示第 \( i \) 条边连接了节点 \( u_i \) 和 \( v_i \)。

输出格式

对于每个 \( k \in [1, n] \)，输出一行整数，表示恰好研究 \( k \) 个魔法装置并返回到根节点的最少时间。

输入输出样例

输入样例 #1

5
1 2
1 3
2 4
2 5

输出样例 #1

0
1
2
4
6

说明

样例解释

• \( k = 1 \)：只需要待在魔法装置 1 处，时间为 0。
• \( k = 2 \)：从魔法装置 1 到魔法装置 2，返回时间为 1。
• \( k = 3 \)：从魔法装置 1 到魔法装置 2，再到魔法装置 4，然后返回，时间为 2。
• \( k = 4 \)：从魔法装置 1 到魔法装置 2，再到魔法装置 4，返回魔法装置 1，再去魔法装置 3，返回魔法装置 1，时间为 4。
• \( k = 5 \)：从魔法装置 1 到魔法装置 3，再返回魔法装置 1，再去魔法装置 2，再到魔法装置 5，返回魔法装置 2，再去魔法装置 4，最后返回魔法装置 1，时间为 6。

数据范围与约定

对于所有数据，\( 1 \leq n \leq 10^5 \)，\( 1 \leq u_i, v_i \leq n \)。