実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 頂点の木が与えられます。頂点には 1,2,\ldots ,N の番号がついており、i 番目の辺は頂点 u_i,v_i を結ぶ無向辺です。
各整数 i\,(1 \leq i \leq N) に対して、\sum_{j=1}^{N}dis(i,j) を求めてください。
ただし、dis(i,j) は頂点 i から頂点 j に到達する際にたどる必要のある最小の辺数です。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N u_1 v_1 u_2 v_2 \vdots u_{N-1} v_{N-1}
出力
N 行出力せよ。
i 行目には \sum_{j=1}^{N}dis(i,j) を出力せよ。
入力例 1
3 1 2 2 3
出力例 1
3 2 3
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3、
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2、
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3、
です。
入力例 2
2 1 2
出力例 2
1 1
入力例 3
6 1 6 1 5 1 3 1 4 1 2
出力例 3
5 9 9 9 9 9
Score : 500 points
Problem Statement
Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.
For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).
Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N u_1 v_1 u_2 v_2 \vdots u_{N-1} v_{N-1}
Output
Print N lines.
The i-th line should contain \sum_{j=1}^{N}dis(i,j).
Sample Input 1
3 1 2 2 3
Sample Output 1
3 2 3
We have:
dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,
dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,
dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.
Sample Input 2
2 1 2
Sample Output 2
1 1
Sample Input 3
6 1 6 1 5 1 3 1 4 1 2
Sample Output 3
5 9 9 9 9 9