C. Colorful Tree

Codeforces

IDCF10225C

Time2000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

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 distinct types of colors appearing on it. Calculate the sum of values of all possible paths, $frac(n (n -1), 2)$ in total, between two different nodes on the tree. The 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. For 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. ## Input The 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. ## Output For 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. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of students. Let $ x, d \in \mathbb{Z}_{\geq 0} $ be the minimum required skill sum and maximum allowed skill difference, respectively. Let $ S = \{s_1, s_2, \dots, s_n\} \subseteq \mathbb{Z}_{\geq 0} $ be the set of student skills. Let $ \mathcal{T} $ be the set of all non-empty subsets $ T \subseteq S $. **Constraints** For each team $ T \in \mathcal{T} $: 1. $ \sum_{t \in T} t \geq x $ 2. $ \max(T) - \min(T) \leq d $ **Objective** Compute $ \left| \left\{ T \in \mathcal{T} \,\middle|\, \sum_{t \in T} t \geq x \text{ and } \max(T) - \min(T) \leq d \right\} \right| $.

API Response (JSON)

{
  "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 ...",
      "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.  \nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments