{"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 one subtree.\n\nThe 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.\n\nEach 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.\n\nPrint \"Yes\" if it is possible to divide the tree into $K$ subtrees of the same size. Otherwise print \"No\".\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint \"Yes\" if it is possible to divide the tree into $K$ subtrees of the same size. Otherwise print \"No\".\n\n[samples]","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. The graph $ T $ is connected and acyclic.  \n\n**Objective**  \nDetermine whether there exists a partition of $ V $ into $ k $ disjoint subsets $ V_1, V_2, \\dots, V_k $ such that:  \n- $ \\bigcup_{i=1}^k V_i = V $,  \n- $ V_i \\cap V_j = \\emptyset $ for all $ i \\ne j $,  \n- For each $ i \\in \\{1, \\dots, k\\} $, the induced subgraph $ T[V_i] $ is a connected subtree,  \n- $ |V_i| = \\frac{n}{k} $ for all $ i \\in \\{1, \\dots, k\\} $.  \n\n**Note**: The partition is valid only if $ k \\mid n $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF102155","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}