题目描述
1 から N までの番号がつけられた N 個の頂点を持つ木があります。この木の i 番目の辺は頂点 ai と bi を結んでいます。 また、各頂点には色が塗られており、 頂点 i に塗られている色は ci です。ここで、各頂点に塗られている色は 1 以上 N 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。
k=1,2,...,N に対して、以下の問題を解いてください。
- 色 k が塗られている頂点を一度以上通るような単純パスの数を求めよ
補足: 頂点 u から頂点 v へ向かう単純パスと、頂点 v から頂点 u へ向かう単純パスは区別しません。
输入格式
入力は以下の形式で標準入力から与えられる。
N c1 c2 ... cN a1 b1 : aN−1 bN−1
输出格式
k=1,2,...,N に対する問題の答えを、順番に改行区切りで出力せよ。
题目大意
题目描述
给定一棵 n 个点的树,给第 i 个点染上颜色 ci,其中,ci 为 [1,n] 的一个整数。
现在,对于每一种颜色 k,你要求出有多少条简单路径满足路径上至少有一个点的颜色为 k。
输入格式
第一行一个整数 n。
接下来一行 n 个整数,表示 ci。
接下来第 3 到第 n+1 行,每行两个整数 ui,vi,描述一条树边。
输出格式
输出 n 行,一行一个整数,分别表示对于颜色 1,2,...,n 的答案。
提示
制約
- 1 ≤ N ≤ 2 × 105
- 1 ≤ ci ≤ N
- 1 ≤ ai,bi ≤ N
- 与えられるグラフは木である。
- 入力はすべて整数である。
Sample Explanation 1
頂点 i と頂点 j を結ぶ単純パスを、Pi,j と表します。 色 1 が塗られている頂点を一度以上通る単純パスは、 P1,1, P1,2, P1,3, P2,3, P3,3 の 5 つあります。 色 2 が塗られている頂点を一度以上通る単純パスは、 P1,2, P1,3, P2,2, P2,3 の 4 つあります。 色 3 が塗られている頂点を一度以上通る単純パスはありません。