5. Tree Division

Codeforces

IDCF102155

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Given a tree of size $n$ and an integer $k$. Your task is to determine if the tree can be divided into k non-intersecting subtrees *of the same size*. Every node of the tree should belong to exactly one subtree. The first line of input contains two integers $n$ and $k$ ($1 <= n, k <= 10^5$), the number of nodes in the tree and the number of subtrees after dividing the tree, respectively. Each of the following $n -1$ lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n$), representing an edge that connects the two nodes. It is guaranteed that the given graph is a tree. Print "Yes" if it is possible to divide the tree into $K$ subtrees of the same size. Otherwise print "No". ## Input The first line of input contains two integers $n$ and $k$ ($1 <= n, k <= 10^5$), the number of nodes in the tree and the number of subtrees after dividing the tree, respectively.Each of the following $n -1$ lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n$), representing an edge that connects the two nodes. It is guaranteed that the given graph is a tree. ## Output Print "Yes" if it is possible to divide the tree into $K$ subtrees of the same size. Otherwise print "No". [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = n $ and $ |E| = n - 1 $. Let $ k \in \mathbb{Z}^+ $ be the number of desired subtrees. **Constraints** 1. $ 1 \leq n, k \leq 10^5 $ 2. The graph $ T $ is connected and acyclic. **Objective** Determine whether there exists a partition of $ V $ into $ k $ disjoint subsets $ V_1, V_2, \dots, V_k $ such that: - $ \bigcup_{i=1}^k V_i = V $, - $ V_i \cap V_j = \emptyset $ for all $ i \ne j $, - For each $ i \in \{1, \dots, k\} $, the induced subgraph $ T[V_i] $ is a connected subtree, - $ |V_i| = \frac{n}{k} $ for all $ i \in \{1, \dots, k\} $. **Note**: The partition is valid only if $ k \mid n $.

API Response (JSON)

{
  "problem": {
    "name": "5. Tree Division",
    "description": {
      "content": "Given a tree of size $n$ and an integer $k$. Your task is to determine if the tree can be divided into k non-intersecting subtrees *of the same size*. Every node of the tree should belong to exactly o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF102155"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a tree of size $n$ and an integer $k$. Your task is to determine if the tree can be divided into k non-intersecting subtrees *of the same size*. Every node of the tree should belong to exactly o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $ and $ |E| = n - 1 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of desired subtrees.\n\n**Constraints**  \n1. $ 1 \\leq n, k \\leq 10^5 $  \n2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments