/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点の木 T が与えられます。i 番目の辺は頂点 A_i と B_i を結んでいます。
次の条件をともに満たす N 頂点の根付き木 R を 1 つ求めてください。
- 1 \leq x < y \leq N を満たす全ての整数の組 (x,y) に対し次が成り立つ
- R における頂点 x,y の最小共通祖先が頂点 z であるとき、T において 頂点 x,y を結ぶ単純パス上に頂点 z が存在する
- R において、根以外の全ての頂点 v に対し、v を根とする部分木の頂点数の 2 倍は、 v の親を根とする部分木の頂点数以下である
なお、この条件を満たす根付き木は必ず存在することが証明できます。
制約
- 1 \leq N \leq 10^5
- 1\leq A_i,B_i \leq N
- 入力は全て整数である
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
出力
問題文中の条件を満たす根付き木を R とする。R における頂点 i の親を頂点 p_i とする（ただし、i が根のときは p_i=-1 と定める）。
N 個の整数 p_1,\ldots,p_N をこの順に空白区切りで出力せよ。
入力例 1
4 1 2 2 3 3 4
出力例 1
2 -1 4 2
例えば、R における頂点 1,3 の最小共通祖先は頂点 2 であり、T において、頂点 1,3 を結ぶ単純パス上に頂点 2 が存在します。
また、例えば、R における頂点 4 を根とする部分木の頂点数は 2 であり、その 2 倍は、頂点 2 を根とする部分木の頂点数 4 以下です。
入力例 2
5 1 2 1 3 1 4 1 5
出力例 2
-1 1 1 1 1
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