問題一覧 > 通常問題

No.1098 LCAs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 135
作問者 : SSRSSSRS / テスター : しのしの
3 ProblemId : 4402 / 出題時の順位表
問題文最終更新日: 2020-06-26 23:29:21

問題文

$N$頂点の根付き木があります。
根付き木の頂点には$1$から$N$の番号がついており、根は頂点$1$です。また、$i (1 \leq i < N)$番目の辺は頂点$v_i$と頂点$w_i$を双方向に結んでいます。
$k=1,2,\cdots,N$について、以下の問題を解いてください。

  • 木の2頂点の組$(v,w)$で、それらの最近共通祖先(LCA)が頂点$k$であるようなものの個数を求めよ。

入力

$N$
$v_1 \ w_1$
$v_2 \ w_2$
$\vdots$
$v_{N-1} \ w_{N-1}$

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $1 \leq N \leq 2\times10^5$
  • $1 \leq v_i, w_i \leq N (1 \leq i < N)$
  • 与えられたグラフは木である

出力

$N$行出力してください。
$i (1 \leq i \leq N)$行目には、$k=i$のときの答えを出力してください。

サンプル

サンプル1
入力
3
1 2
1 3
出力
7
1
1

頂点$v$と頂点$w$のLCAが頂点$1$になるような$(v,w)$の組は、$(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)$の$7$つあります。
頂点$v$と頂点$w$のLCAが頂点$2$になるような$(v,w)$の組は、$(2,2)$の$1$つのみです。
頂点$v$と頂点$w$のLCAが頂点$3$になるような$(v,w)$の組は、$(3,3)$の$1$つのみです。
よって、$k=1,2,3$に対する答えはそれぞれ$7,1,1$となります。

サンプル2
入力
5
1 2
2 3
3 4
3 5
出力
9
7
7
1
1

サンプル3
入力
1
出力
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。