No.3272 Separate Contractions
タグ : / 解いたユーザー数 11
作問者 :
apricity
/ テスター :
遭難者
問題文
木 $U$ に対して， $U$ のスコアを $\displaystyle \sum_{x \in V}\, \max_{y \in V}\, \operatorname{d}(x,y)$ と定義します．ただし $V$ は $U$ の頂点集合， $\operatorname{d} (x,y)$ は $U$ 上での頂点 $x$ と頂点 $y$ の距離，すなわち $x$ から $y$ に移動する際に用いる辺の本数の最小値を表します．
つまり， $U$ のスコアは「 $U$ の全ての頂点 $x$ について， $x$ から最も遠い頂点までの距離を足し合わせた値」です．
頂点に $1$ から $N$ までの番号がついた $N$ 頂点の木 $T$ が与えられます． $T$ の $i$ 番目の辺 $e_i$ は頂点 $a_i$ と頂点 $b_i$ を結びます．
$k = 1,2,\dots,N-1$ について， $T$ から辺 $e_k$ を縮約してできる $N-1$ 頂点の木 $T/e_k$ のスコアを求めてください．
入力
$N$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{N-1}\ b_{N-1}$
- 入力は全て整数
- $2 \le N \le 2 \times 10^5$
- $1 \le a_i, b_i \le N$
- 与えられるグラフは木
出力
$N-1$ 行出力してください． $k$ 行目 $(1 \le k \le N-1)$ には，$T/e_k$ のスコアを出力してください．
サンプル
サンプル1
入力
5 1 2 2 3 3 4 3 5
出力
7 7 10 10
$T$ を以下に図示します．
$T/e_1,\ T/e_2,\ T/e_3,\ T/e_4$ を以下に図示します．図中の $a/b$ は，縮約の際に頂点 $a$ と $b$ が併合されてできる新たな頂点を表します．
$T/e_1$ のスコアは以下のように計算されます．
- 頂点 $1/2$ から最も遠い頂点までの距離は $2$ です．
- 頂点 $3$ から最も遠い頂点までの距離は $1$ です．
- 頂点 $4$ から最も遠い頂点までの距離は $2$ です．
- 頂点 $5$ から最も遠い頂点までの距離は $2$ です．
- よって， $T/e_1$ のスコアは $2+1+2+2 = 7$ です．
$T/e_3$ のスコアは以下のように計算されます．
- 頂点 $1$ から最も遠い頂点までの距離は $3$ です．
- 頂点 $2$ から最も遠い頂点までの距離は $2$ です．
- 頂点 $3/4$ から最も遠い頂点までの距離は $2$ です．
- 頂点 $5$ から最も遠い頂点までの距離は $3$ です．
- よって， $T/e_3$ のスコアは $3+2+2+3 = 10$ です．
サンプル2
入力
2 1 2
出力
0
$T/e_1$ は $1$ 頂点 $0$ 辺の木なので，そのスコアは $0$ です．
サンプル3
入力
10 1 2 2 3 2 4 4 5 4 6 6 7 7 8 7 9 9 10
出力
43 43 38 44 37 37 44 38 38
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。