{"problem":{"name":"path pass i","description":{"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_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc163_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc163_f","tags":[],"sample_group":[["3\n1 2 1\n1 2\n2 3","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."],["1\n1","1"],["2\n1 2\n1 2","2\n2"],["5\n1 2 3 4 5\n1 2\n2 3\n3 4\n3 5","5\n8\n10\n5\n5"],["8\n2 7 2 5 4 1 7 5\n3 1\n1 2\n2 7\n4 5\n5 6\n6 8\n7 8","18\n15\n0\n14\n23\n0\n23\n0"]],"created_at":"2026-03-03 11:01:13"}}