AT_abc337_g [ABC337G] Tree Inversion

[problemUrl]: https://atcoder.jp/contests/abc337/tasks/abc337_g 頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ N $ の $ N $ 頂点からなる木 $ T $ が与えられます。 $ i $ 番目 $ (1\leq\ i\lt\ N) $ の辺は頂点 $ u\ _\ i $ と頂点 $ v\ _\ i $ を結んでいます。 $ T $ の頂点 $ u $ について $ f(u) $ を次のように定めます。 - $ f(u)\coloneqq $ $ T $ の頂点 $ v $ と頂点 $ w $ の組であって、次の $ 2 $ つの条件を満たすものの個数 - 頂点 $ u $ と頂点 $ v $ を結ぶパス上に頂点 $ w $ が含まれる。 - $ v\lt\ w $ ただし、「頂点 $ u $ と頂点 $ v $ を結ぶパス上に頂点 $ w $ が含まれる」は、$ u=w $ や $ v=w $ のときにも成立するとします。 $ f(1),f(2),\ldots,f(N) $ の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u\ _\ 1 $ $ v\ _\ 1 $ $ u\ _\ 2 $ $ v\ _\ 2 $ $ \vdots $ $ u\ _\ {N-1} $ $ v\ _\ {N-1} $

$ f(1),f(2),\ldots,f(N) $ の値をこの順に空白を区切りとして出力せよ。

### 制約 - $ 2\leq\ N\leq2\times10\ ^\ 5 $ - $ 1\leq\ u\ _\ i\leq\ N\ (1\leq\ i\leq\ N) $ - $ 1\leq\ v\ _\ i\leq\ N\ (1\leq\ i\leq\ N) $ - 与えられるグラフは木 - 入力はすべて整数 ### Sample Explanation 1 与えられる木は以下のようになります。 !\[\](https://img.atcoder.jp/abc337/f02c6287abee93272dda64faf9499a81.png) 例えば、$ f(4)=4 $ です。 実際、$ u=4 $ に対して $ (v,w)=(1,2),(1,4),(2,4),(3,4) $ の $ 4 $ 通りが条件を満たします。 ### Sample Explanation 2 与えられる木は以下のようになります。 !\[\](https://img.atcoder.jp/abc337/e59ed095480b6f8ec4ecfc212f14e635.png) $ f(14) $ の値は、数列 $ (14,9,1,6,12,2,15,4,11,13,3,8,10,7,5) $ の転倒数 $ 57 $ になります。