B. Ktree

Codeforces

IDCF10100B

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You are given a tree consisting of N nodes and N - 1 weighted edges. You want to remove exactly M edges so that node 1 will remain in a component with exactly K nodes, while minimizing the sum of costs of the removed edges. The first line of input will contain three positive integers N(1 ≤ N < 75), M(1 ≤ M < N) and K(1 ≤ K ≤ N). The following N - 1 lines will each contain 3 numbers x y c, describing an edge between nodes x and y of cost c. The first and only line of your output should contain one integer representing the minimum cost required, or - 1 if there is no valid solution. ## Input The first line of input will contain three positive integers N(1 ≤ N < 75), M(1 ≤ M < N) and K(1 ≤ K ≤ N). The following N - 1 lines will each contain 3 numbers x y c, describing an edge between nodes x and y of cost c. ## Output The first and only line of your output should contain one integer representing the minimum cost required, or - 1 if there is no valid solution. [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = N $ nodes and $ |E| = N - 1 $ weighted edges. Let $ w: E \to \mathbb{R}^+ $ be the edge cost function. Let $ M, K \in \mathbb{Z}^+ $ with $ 1 \leq M < N $, $ 1 \leq K \leq N $. **Constraints** 1. Remove exactly $ M $ edges from $ T $. 2. After removal, the connected component containing node $ 1 $ must contain exactly $ K $ nodes. 3. The remaining graph consists of $ M+1 $ connected components. **Objective** Minimize the total cost of the removed edges: $$ \min \sum_{e \in R} w(e) $$ where $ R \subseteq E $, $ |R| = M $, and the component containing node $ 1 $ in $ T \setminus R $ has size $ K $. If no such $ R $ exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "B. Ktree",
    "description": {
      "content": "You are given a tree consisting of N nodes and N - 1 weighted edges. You want to remove exactly M edges so that node 1 will remain in a component with exactly K nodes, while minimizing the sum of cost",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10100B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree consisting of N nodes and N - 1 weighted edges. You want to remove exactly M edges so that node 1 will remain in a component with exactly K nodes, while minimizing the sum of cost...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = N $ nodes and $ |E| = N - 1 $ weighted edges.  \nLet $ w: E \\to \\mathbb{R}^+ $ be the edge cost function.  \nLet $ M, K \\in \\mathbb{Z}^+ $ wit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments