P5588 Peppa Pig Climbs a Tree

Peppa and George are climbing a tree. Given a tree $T(V,E)$ with $n$ nodes, the color of node $i$ is $w_i$, and it is guaranteed that $1 \leq w_i \leq n$. For each $1 \leq i \leq n$, output how many pairs $(u,v)$ satisfy $u

The first line contains one positive integer $n$. The second line contains $n$ positive integers, where the $i$-th integer is $w_i$. The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge $(u,v)$ in $T$.

Output $n$ lines, each containing one positive integer. On the $i$-th line, output the number of paths that contain all nodes whose color is $i$.

 For the first sample. For color $1$, the pairs $(1,2),(1,3),(1,4)$ satisfy the condition. For color $2$, the pairs $(1,3),(1,4),(2,3),(2,4)$ satisfy the condition. For color $3$, the pairs $(1,4),(2,4),(3,4)$ satisfy the condition. For color $4$, since there is no node with color $4$ in the graph, all pairs satisfy the condition. ### Constraints For $40\%$ of the testdata, $n \leq 10^2$. For $60\%$ of the testdata, $n \leq 10^3$. For $100\%$ of the testdata, $n \leq 10^6$. Translated by ChatGPT 5