P2664 Game on a Tree

lrb has a tree, and each node has a color. Given a color sequence of length $n$, define $s(i, j)$ as the number of distinct colors on the simple path from node $i$ to node $j$. $$sum_i=\sum_{j=1}^n s(i, j)$$ Now he wants you to compute all $sum_i$. For $40\%$ of the testdata, $n \leq 2000$. For $100\%$ of the testdata, $1 \leq n, c_i \leq 10^5$.

The first line contains an integer $n$, the number of nodes in the tree. The second line contains $n$ integers, the colors of the $n$ nodes: $c_1, c_2, \ldots, c_n$. Each of the next $n-1$ lines contains two integers $x, y$, meaning there is an edge between $x$ and $y$.

Output $n$ lines. The $i$-th line should be $sum_i$.

$$sum_1=s(1,1)+s(1,2)+s(1,3)+s(1,4)+s(1,5)=1+2+3+2+2=10$$ $$sum_2=s(2,1)+s(2,2)+s(2,3)+s(2,4)+s(2,5)=2+1+2+1+3=9$$ $$sum_3=s(3,1)+s(3,2)+s(3,3)+s(3,4)+s(3,5)=3+2+1+2+3=11$$ $$sum_4=s(4,1)+s(4,2)+s(4,3)+s(4,4)+s(4,5)=2+1+2+1+3=9$$ $$sum_5=s(5,1)+s(5,2)+s(5,3)+s(5,4)+s(5,5)=2+3+3+3+1=12$$ Translated by ChatGPT 5