AT_ttpc2019_m Inversion Numbers of Tree

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_m $ 1 $ から $ N $ までの番号がつけられた $ N $ 個の頂点を持つ木があります。 この木の $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 この木に対し、頂点 $ r $ を根としたときの転倒数を以下のように定義します。 - 頂点 $ r $ から頂点 $ u $ の単純パスの端点または辺上に頂点 $ v $ が含まれるような組 $ (u,\ v)\ (u\ \lt\ v) $ の個数 $ 1 $ 以上 $ N $ 以下の全ての整数 $ r $ に対し、頂点 $ r $ を根としたときの転倒数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

$ N $ 行出力せよ。$ i $ 行目には頂点 $ i $ を根としたときの転倒数を出力すること。

### 制約 - 入力は全て整数 - $ 2\ \leq\ N\ \leq\ 10^{5} $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ - 与えられるグラフは木である。 ### Sample Explanation 1 \- 頂点 $ 1 $ を根としたときの転倒数は、$ (u,\ v)\ =\ (2,\ 3) $ より $ 1 $ です - 頂点 $ 2 $ を根としたときの転倒数は、$ (u,\ v)\ =\ (1,\ 2),\ (1,\ 3) $ より $ 2 $ です - 頂点 $ 3 $ を根としたときの転倒数は、$ (u,\ v)\ =\ (1,\ 3),\ (2,\ 3) $ より $ 2 $ です。