No.3272 Separate Contractions
Problem Statement
For a tree $U$, define the score of $U$ as $\displaystyle \sum_{x \in V}\, \max_{y \in V}\, \operatorname{d}(x,y)$. Here, $V$ is the vertex set of $U$, and $\operatorname{d} (x,y)$ denotes the distance between vertex $x$ and vertex $y$ on $U$, that is, the minimum number of edges used when moving from $x$ to $y$.
In other words, the score of $U$ is "the sum, over all vertices $x$ of $U$, of the distance from $x$ to the vertex farthest from it".
You are given a tree $T$ with $N$ vertices numbered from $1$ to $N$. The $i$-th edge $e_i$ of $T$ connects vertex $a_i$ and vertex $b_i$.
For each $k = 1,2,\dots,N-1$, find the score of the tree $T/e_k$ with $N-1$ vertices obtained by contracting the edge $e_k$ of $T$.
Input
$N$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{N-1}\ b_{N-1}$
- All input values are integers.
- $2 \le N \le 2 \times 10^5$
- $1 \le a_i, b_i \le N$
- The given graph is a tree.
Output
Print $N-1$ lines. On the $k$-th line $(1 \le k \le N-1)$, print the score of $T/e_k$.
Sample
Sample 1
Input
5 1 2 2 3 3 4 3 5
Output
7 7 10 10
$T$ is illustrated below.
$T/e_1,\ T/e_2,\ T/e_3,\ T/e_4$ are illustrated below. In the figure, $a/b$ represents the new vertex formed by merging vertices $a$ and $b$ during the contraction.
The score of $T/e_1$ is calculated as follows.
- The distance from vertex $1/2$ to the vertex farthest from it is $2$.
- The distance from vertex $3$ to the vertex farthest from it is $1$.
- The distance from vertex $4$ to the vertex farthest from it is $2$.
- The distance from vertex $5$ to the vertex farthest from it is $2$.
- Therefore, the score of $T/e_1$ is $2+1+2+2 = 7$.
The score of $T/e_3$ is calculated as follows.
- The distance from vertex $1$ to the vertex farthest from it is $3$.
- The distance from vertex $2$ to the vertex farthest from it is $2$.
- The distance from vertex $3/4$ to the vertex farthest from it is $2$.
- The distance from vertex $5$ to the vertex farthest from it is $3$.
- Therefore, the score of $T/e_3$ is $3+2+2+3 = 10$.
Sample 2
Input
2 1 2
Output
0
$T/e_1$ is a tree with $1$ vertex and $0$ edges, so its score is $0$.
Sample 3
Input
10 1 2 2 3 2 4 4 5 4 6 6 7 7 8 7 9 9 10
Output
43 43 38 44 37 37 44 38 38
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity