問題一覧 > 通常問題

No.3272 Separate Contractions

レベル : / AI推定難易度 : 2475 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : apricity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 12470 / 自分の提出
問題文最終更新日: 2025-09-10 19:12:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 482 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。