{"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 costs of the removed edges.\n\nThe 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.\n\nThe first and only line of your output should contain one integer representing the minimum cost required, or  - 1 if there is no valid solution.\n\n## Input\n\nThe 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.\n\n## Output\n\nThe first and only line of your output should contain one integer representing the minimum cost required, or  - 1 if there is no valid solution.\n\n[samples]","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}^+ $ with $ 1 \\leq M < N $, $ 1 \\leq K \\leq N $.  \n\n**Constraints**  \n1. Remove exactly $ M $ edges from $ T $.  \n2. After removal, the connected component containing node $ 1 $ must contain exactly $ K $ nodes.  \n3. The remaining graph consists of $ M+1 $ connected components.  \n\n**Objective**  \nMinimize the total cost of the removed edges:  \n$$\n\\min \\sum_{e \\in R} w(e)\n$$  \nwhere $ R \\subseteq E $, $ |R| = M $, and the component containing node $ 1 $ in $ T \\setminus R $ has size $ K $.  \nIf no such $ R $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10100B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}