D. Divide a Tree

Codeforces

IDCF10282D

Time10000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Fish has a tree with $N$ nodes numbered from $1$ to $N$, and for each node there is a label attached to it. These labels are integers ranging from $1$ to $N$. Now Fish wants to divide the tree into many parts and each part is a connected component in the tree. There are so many ways to achieve it, right? But now Fish defines a part as a *good* part if there is at least one label appears only in this part. Please tell Fish how many *good* parts he can get at most in one division. The first line of input contains an integer $T$, representing the number of test cases. Then for each test case: The first line contains one integer $N$ as mentioned above. The second line contains $N$ integers, representing the label for each node. Then $N -1$ lines follow, each line containing two numbers $a, b$, which means that there is an edge connecting node $a$ and node $b$. For each test case, you should output *Case $x$: $y$*, where $x$ indicates the case number starting from $1$, and $y$ is the number of *good* parts Fish can get at most in one division. $1 <= T <= 100$ $1 <= N <= 10^5$ $1 <= a, b <= N$ For $90 %$ test cases: $N <= 1000$ ## Input The first line of input contains an integer $T$, representing the number of test cases.Then for each test case:The first line contains one integer $N$ as mentioned above.The second line contains $N$ integers, representing the label for each node.Then $N -1$ lines follow, each line containing two numbers $a, b$, which means that there is an edge connecting node $a$ and node $b$. ## Output For each test case, you should output *Case $x$: $y$*, where $x$ indicates the case number starting from $1$, and $y$ is the number of *good* parts Fish can get at most in one division. [samples] ## Note $1 <= T <= 100$$1 <= N <= 10^5$$1 <= a, b <= N$For $90 %$ test cases: $N <= 1000$

**Definitions** Let $ n, m, s \in \mathbb{Z} $ with $ 1 \leq s \leq n \leq 10^5 $, $ 0 \leq m \leq 2 \cdot 10^5 $. Let $ G = (V, E) $ be a directed graph where $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $ is the set of $ m $ already proved implications: $ E = \{(u_i, v_i) \mid i \in \{1, \dots, m\}\} $. Let $ \overline{E} $ denote the transitive closure of $ E $: i.e., $ (u, v) \in \overline{E} $ iff there exists a directed path from $ u $ to $ v $ in $ G $. **Constraints** 1. $ 1 \leq s \leq n $ 2. $ 1 \leq u_i, v_i \leq n $ for all $ i \in \{1, \dots, m\} $ **Objective** Compute the number of ordered pairs $ (x, y) $ involving $ s $ (i.e., $ x = s $ or $ y = s $, but $ x \ne y $) such that $ (x, y) \notin E $ but $ (x, y) \in \overline{E} $. That is, count: $$ \left| \left( \{s\} \times (V \setminus \{s\}) \cup (V \setminus \{s\}) \times \{s\} \right) \cap \overline{E} \setminus E \right| $$

API Response (JSON)

{
  "problem": {
    "name": "D. Divide a Tree",
    "description": {
      "content": "Fish has a tree with $N$ nodes numbered from $1$ to $N$, and for each node there is a label attached to it. These labels are integers ranging from $1$ to $N$. Now Fish wants to divide the tree into ma",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10282D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Fish has a tree with $N$ nodes numbered from $1$ to $N$, and for each node there is a label attached to it. These labels are integers ranging from $1$ to $N$. Now Fish wants to divide the tree into ma...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, s \\in \\mathbb{Z} $ with $ 1 \\leq s \\leq n \\leq 10^5 $, $ 0 \\leq m \\leq 2 \\cdot 10^5 $.  \nLet $ G = (V, E) $ be a directed graph where $ V = \\{1, 2, \\dots, n\\} $ and $ E \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments