{"problem":{"name":"F. Tree Destruction","description":{"content":"You are given an unweighted tree with _n_ vertices. Then _n_ - 1 following operations are applied to the tree. A single operation consists of the following steps: 1.  choose two leaves; 2.  add the l","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF911F"},"statements":[{"statement_type":"Markdown","content":"You are given an unweighted tree with _n_ vertices. Then _n_ - 1 following operations are applied to the tree. A single operation consists of the following steps:\n\n1.  choose two leaves;\n2.  add the length of the simple path between them to the answer;\n3.  remove one of the chosen leaves from the tree.\n\nInitial answer (before applying operations) is 0. Obviously after _n_ - 1 such operations the tree will consist of a single vertex.\n\nCalculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!\n\n## Input\n\nThe first line contains one integer number _n_ (2 ≤ _n_ ≤ 2·105) — the number of vertices in the tree.\n\nNext _n_ - 1 lines describe the edges of the tree in form _a__i_, _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_). It is guaranteed that given graph is a tree.\n\n## Output\n\nIn the first line print one integer number — maximal possible answer.\n\nIn the next _n_ - 1 lines print the operations in order of their applying in format _a__i_, _b__i_, _c__i_, where _a__i_, _b__i_ — pair of the leaves that are chosen in the current operation (1 ≤ _a__i_, _b__i_ ≤ _n_), _c__i_ (1 ≤ _c__i_ ≤ _n_, _c__i_ = _a__i_ or _c__i_ = _b__i_) — choosen leaf that is removed from the tree in the current operation.\n\nSee the examples for better understanding.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一棵具有 #cf_span[n] 个顶点的无权树。随后对这棵树应用 #cf_span[n - 1] 次操作。单次操作包含以下步骤：\n\n初始答案（应用操作前）为 #cf_span[0]。显然，在应用 #cf_span[n - 1] 次这样的操作后，树将只剩一个顶点。\n\n请计算你能获得的最大可能答案，并构造一个操作序列以达到该答案！\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 树的顶点数。\n\n接下来 #cf_span[n - 1] 行以 #cf_span[ai, bi] 的形式描述树的边（#cf_span[1 ≤ ai], #cf_span[bi ≤ n], #cf_span[ai ≠ bi]）。保证给定图是一棵树。\n\n第一行输出一个整数 —— 最大可能的答案。\n\n接下来的 #cf_span[n - 1] 行按操作应用顺序输出操作，格式为 #cf_span[ai, bi, ci]，其中 #cf_span[ai, bi] 是当前操作中选择的两个叶子节点（#cf_span[1 ≤ ai], #cf_span[bi ≤ n]），#cf_span[ci]（#cf_span[1 ≤ ci ≤ n], #cf_span[ci = ai] 或 #cf_span[ci = bi]）是当前操作中从树中移除的叶子节点。\n\n详见示例以更好地理解。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 树的顶点数。接下来 #cf_span[n - 1] 行以 #cf_span[ai, bi] 的形式描述树的边（#cf_span[1 ≤ ai], #cf_span[bi ≤ n], #cf_span[ai ≠ bi]）。保证给定图是一棵树。\n\n## Output\n\n第一行输出一个整数 —— 最大可能的答案。接下来的 #cf_span[n - 1] 行按操作应用顺序输出操作，格式为 #cf_span[ai, bi, ci]，其中 #cf_span[ai, bi] 是当前操作中选择的两个叶子节点（#cf_span[1 ≤ ai], #cf_span[bi ≤ n]），#cf_span[ci]（#cf_span[1 ≤ ci ≤ n], #cf_span[ci = ai] 或 #cf_span[ci = bi]）是当前操作中从树中移除的叶子节点。详见示例以更好地理解。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be an unweighted tree with $ n \\geq 2 $ vertices and $ n-1 $ edges.  \nLet $ A_0 = 0 $ be the initial answer.  \nEach operation removes one leaf node $ c_i $ from the current tree, and adds the distance $ d(a_i, b_i) $ between two chosen leaves $ a_i, b_i $ to the answer.  \nAfter $ n-1 $ operations, only one vertex remains.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $  \n2. The graph is a tree.  \n3. In each operation:  \n   - $ a_i, b_i $ are leaves of the current tree.  \n   - $ c_i \\in \\{a_i, b_i\\} $ is the leaf removed.  \n   - The tree remains connected after removal.  \n\n**Objective**  \nMaximize the final answer:  \n$$\nA_{n-1} = \\sum_{i=1}^{n-1} d(a_i, b_i)\n$$  \nand construct a sequence of operations $ \\{(a_i, b_i, c_i)\\}_{i=1}^{n-1} $ achieving this maximum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF911F","tags":["constructive algorithms","dfs and similar","graphs","greedy","trees"],"sample_group":[["3\n1 2\n1 3","3\n2 3 3\n2 1 1"],["5\n1 2\n1 3\n2 4\n2 5","9\n3 5 5\n4 3 3\n4 1 1\n4 2 2"]],"created_at":"2026-03-03 11:00:39"}}