{"raw_statement":[{"iden":"problem statement","content":"We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge in this tree connects Vertex $a_i$ and $b_i$. Additionally, each vertex is painted in a color, and the color of Vertex $i$ is $c_i$. Here, the color of each vertex is represented by an integer between $1$ and $N$ (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.\nFor each $k=1, 2, ..., N$, solve the following problem:\n\n*   Find the number of simple paths that visit a vertex painted in the color $k$ one or more times.\n\n**Note:** The simple paths from Vertex $u$ to $v$ and from $v$ to $u$ are not distinguished."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq c_i \\leq N$\n*   $1 \\leq a_i,b_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$c_1$ $c_2$ $...$ $c_N$\n$a_1$ $b_1$\n$:$\n$a_{N-1}$ $b_{N-1}$"},{"iden":"sample input 1","content":"3\n1 2 1\n1 2\n2 3"},{"iden":"sample output 1","content":"5\n4\n0\n\nLet $P_{i,j}$ denote the simple path connecting Vertex $i$ and $j$.\nThere are $5$ simple paths that visit a vertex painted in the color $1$ one or more times:  \n$P_{1,1}\\,,\\,$ $P_{1,2}\\,,\\,$ $P_{1,3}\\,,\\,$ $P_{2,3}\\,,\\,$ $P_{3,3}$\nThere are $4$ simple paths that visit a vertex painted in the color $2$ one or more times:  \n$P_{1,2}\\,,\\,$ $P_{1,3}\\,,\\,$ $P_{2,2}\\,,\\,$ $P_{2,3}$\nThere are no simple paths that visit a vertex painted in the color $3$ one or more times."},{"iden":"sample input 2","content":"1\n1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"2\n1 2\n1 2"},{"iden":"sample output 3","content":"2\n2"},{"iden":"sample input 4","content":"5\n1 2 3 4 5\n1 2\n2 3\n3 4\n3 5"},{"iden":"sample output 4","content":"5\n8\n10\n5\n5"},{"iden":"sample input 5","content":"8\n2 7 2 5 4 1 7 5\n3 1\n1 2\n2 7\n4 5\n5 6\n6 8\n7 8"},{"iden":"sample output 5","content":"18\n15\n0\n14\n23\n0\n23\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}