Background

— It seems that something called the "Sun" used to exist.

The legend goes like this: white flames gave off dazzling light, and the sky was a clear, pure blue.

It is said that the "Great War" started by the gods and their creations turned the land into scorched earth, and ashes covered the sky.

The ashes struck the power of the stars flowing in the sky — the "Elf Corridor" — which began to glow and dyed the sky red.

And that red color covered every piece of land where mutual slaughter still continued.

Or perhaps it was the planet’s own wail of grief and the blood it shed...

Under the blood-red sky, there was only — blue ash drifting down.

Come back 3579, my proudest faith/ll

Problem Description

Rick discovered an ancient "Divine Tree" within sight.

The Divine Tree is a tree with $n$ positions that contain magical devices. After an initial "survey", there are $n - 1$ magical edges. The $i$-th edge $(1 \leq i \leq n - 1)$ connects two devices $u_i, v_i$, and it is guaranteed that $u_i \neq v_i$ and $1 \leq u_i, v_i \leq n$. These two devices can be traveled between bidirectionally in $1$ unit of time. It is guaranteed that with only these $n - 1$ edges, every device is reachable from every other device.

In addition, there are $n - 1$ special edges. For each device $i \in [2, n]$, you can teleport instantly to device $1$ with cost $0$ time. All special edges can be used only once in total.

Rick starts at device $1$. Now, given the structure of this "Divine Tree", Rick wants to study as many devices as possible within some amount of time. We assume that studying a device only requires arriving at that device, and costs no extra time.

You need to compute as quickly as possible, for all $k \in [1, n]$, if Rick wants to study exactly $k$ different devices, and then return to device $\bm 1$, what is the minimum time needed.

Input Format

The first line contains an integer $n$.

The next $n - 1$ lines each contain two integers $u_i, v_i$.

Output Format

Output $n$ lines in total. The $i$-th line contains one integer, the answer for $k = i$.

5
1 2
1 3
2 4
2 5

0
1
2
4
6

见下发的 hope/hope2.in

见下发的 hope/hope2.ans

Hint

[Sample Explanation $\bm 1$]

• When $k = 1$, Rick only needs to stay at device $1$.
• When $k = 2$, Rick’s route can be $1 \rightarrow 2 \Rightarrow 1$.
• When $k = 3$, Rick’s route can be $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$.
• When $k = 4$, Rick’s route can be $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3 \rightarrow 1$.
• When $k = 5$, Rick’s route can be $1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$.

[Sample Explanation $\bm 2$]

This testdata satisfies the properties of test points numbered $13 \sim 20$.

[Constraints and Conventions]

For all data, $1 \leq n \leq 10^5$, $1 \leq u_i, v_i \leq n$.

Translated by ChatGPT 5