{"problem":{"name":"C. Colorful Tree","description":{"content":"There is a tree having $n$ nodes, the $i$-th node of which has a type of color, denoted by an integer $c_i$. The path between every two nodes is unique, of which we define the value is the number of ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225C"},"statements":[{"statement_type":"Markdown","content":"There is a tree having $n$ nodes, the $i$-th node of which has a type of color, denoted by an integer $c_i$.\n\nThe path between every two nodes is unique, of which we define the value is the number of distinct types of colors appearing on it.\n\nCalculate the sum of values of all possible paths, $frac(n (n -1), 2)$ in total, between two different nodes on the tree.\n\nThe input contains multiple (about $50$) test cases.\n\nFor each test case, the first line contains an integer $n$ ($2 <= n <= 2 times 10^5$), indicating the number of nodes.\n\nThe next line contains $n$ integers, the $i$-th number of which is $c_i$ ($1 <= c_i <= n$), denoting the color of the $i$-th node.\n\nEach of the next $(n -1)$ lines contains two integers $x$, $y$ ($1 <= x, y <= n$, $x eq.not y$), representing an edge between the $x$-th node and the $y$-th one. It is guaranteed that given edges form a tree.\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n## Input\n\nThe input contains multiple (about $50$) test cases.For each test case, the first line contains an integer $n$ ($2 <= n <= 2 times 10^5$), indicating the number of nodes.The next line contains $n$ integers, the $i$-th number of which is $c_i$ ($1 <= c_i <= n$), denoting the color of the $i$-th node.Each of the next $(n -1)$ lines contains two integers $x$, $y$ ($1 <= x, y <= n$, $x eq.not y$), representing an edge between the $x$-th node and the $y$-th one. It is guaranteed that given edges form a tree.\n\n## Output\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of students.  \nLet $ x, d \\in \\mathbb{Z}_{\\geq 0} $ be the minimum required skill sum and maximum allowed skill difference, respectively.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} \\subseteq \\mathbb{Z}_{\\geq 0} $ be the set of student skills.\n\nLet $ \\mathcal{T} $ be the set of all non-empty subsets $ T \\subseteq S $.\n\n**Constraints**  \nFor each team $ T \\in \\mathcal{T} $:  \n1. $ \\sum_{t \\in T} t \\geq x $  \n2. $ \\max(T) - \\min(T) \\leq d $\n\n**Objective**  \nCompute $ \\left| \\left\\{ T \\in \\mathcal{T} \\,\\middle|\\, \\sum_{t \\in T} t \\geq x \\text{ and } \\max(T) - \\min(T) \\leq d \\right\\} \\right| $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}