AT_abc163_f [ABC163F] path pass i

[problemUrl]: https://atcoder.jp/contests/abc163/tasks/abc163_f $ 1 $ から $ N $ までの番号がつけられた $ N $ 個の頂点を持つ木があります。この木の $ i $ 番目の辺は頂点 $ a_i $ と $ b_i $ を結んでいます。 また、各頂点には色が塗られており、 頂点 $ i $ に塗られている色は $ c_i $ です。ここで、各頂点に塗られている色は $ 1 $ 以上 $ N $ 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。 $ k=1,2,...,N $ に対して、以下の問題を解いてください。 - 色 $ k $ が塗られている頂点を一度以上通るような単純パスの数を求めよ **補足:** 頂点 $ u $ から頂点 $ v $ へ向かう単純パスと、頂点 $ v $ から頂点 $ u $ へ向かう単純パスは区別しません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ c_1 $ $ c_2 $ $ ... $ $ c_N $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $

$ k=1,2,...,N $ に対する問題の答えを、順番に改行区切りで出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ c_i\ \leq\ N $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - 与えられるグラフは木である。 - 入力はすべて整数である。 ### Sample Explanation 1 頂点 $ i $ と頂点 $ j $ を結ぶ単純パスを、$ P_{i,j} $ と表します。 色 $ 1 $ が塗られている頂点を一度以上通る単純パスは、 $ P_{1,1}\,,\, $ $ P_{1,2}\,,\, $ $ P_{1,3}\,,\, $ $ P_{2,3}\,,\, $ $ P_{3,3} $ の $ 5 $ つあります。 色 $ 2 $ が塗られている頂点を一度以上通る単純パスは、 $ P_{1,2}\,,\, $ $ P_{1,3}\,,\, $ $ P_{2,2}\,,\, $ $ P_{2,3} $ の $ 4 $ つあります。 色 $ 3 $ が塗られている頂点を一度以上通る単純パスはありません。