102917: [Atcoder]ABC291 Ex - Balanced Tree
Description
Score : $600$ points
Problem Statement
You are given a tree $T$ with $N$ vertices. The $i$-th edge connects vertices $A_i$ and $B_i$.
Construct an $N$-vertex rooted tree $R$ that satisfies the following conditions.
- For all integer pairs $(x,y)$ such that $1 \leq x < y \leq N$,
- if the lowest common ancestor in $R$ of vertices $x$ and $y$ is vertex $z$, then vertex $z$ in $T$ is on the simple path between vertices $x$ and $y$.
- In $R$, for all vertices $v$ except for the root, the number of vertices of the subtree rooted at $v$, multiplied by $2$, does not exceed the number of vertices of the subtree rooted at the parent of $v$.
We can prove that such a rooted tree always exists.
Constraints
- $1 \leq N \leq 10^5$
- $1\leq A_i,B_i \leq N$
- All values in the input are integers.
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$
Output
Let $R$ be a rooted tree that satisfies the conditions in the Problem Statement. Suppose that the parent of vertex $i$ in $R$ is vertex $p_i$. (If $i$ is the root, let $p_i=-1$.)
Print $N$ integers $p_1,\ldots,p_N$, with spaces in between.
Sample Input 1
4 1 2 2 3 3 4
Sample Output 1
2 -1 4 2
For example, the lowest common ancestor in $R$ of vertices $1$ and $3$ is vertex $2$; in $T$, vertex $2$ is on the simple path between vertices $1$ and $3$.
Also, for example, in $R$, the subtree rooted at vertex $4$ has two vertices, and the number multiplied by two does not exceed the number of vertices of the subtree rooted at vertex $2$, which has $4$ vertices.
Sample Input 2
5 1 2 1 3 1 4 1 5
Sample Output 2
-1 1 1 1 1