English · Original
Chinese · Translation
Formal · Original
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 length of the simple path between them to the answer;
3. remove one of the chosen leaves from the tree.
Initial answer (before applying operations) is 0. Obviously after _n_ - 1 such operations the tree will consist of a single vertex.
Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!
## Input
The first line contains one integer number _n_ (2 ≤ _n_ ≤ 2·105) — the number of vertices in the tree.
Next _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.
## Output
In the first line print one integer number — maximal possible answer.
In 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.
See the examples for better understanding.
[samples]
你被给定一棵具有 #cf_span[n] 个顶点的无权树。随后对这棵树应用 #cf_span[n - 1] 次操作。单次操作包含以下步骤：
初始答案（应用操作前）为 #cf_span[0]。显然，在应用 #cf_span[n - 1] 次这样的操作后，树将只剩一个顶点。
请计算你能获得的最大可能答案，并构造一个操作序列以达到该答案！
第一行包含一个整数 #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]）。保证给定图是一棵树。
第一行输出一个整数 —— 最大可能的答案。
接下来的 #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]）是当前操作中从树中移除的叶子节点。
详见示例以更好地理解。
## Input
第一行包含一个整数 #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]）。保证给定图是一棵树。
## Output
第一行输出一个整数 —— 最大可能的答案。接下来的 #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]）是当前操作中从树中移除的叶子节点。详见示例以更好地理解。
[samples]
**Definitions**
Let $ T = (V, E) $ be an unweighted tree with $ n \geq 2 $ vertices and $ n-1 $ edges.
Let $ A_0 = 0 $ be the initial answer.
Each 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.
After $ n-1 $ operations, only one vertex remains.
**Constraints**
1. $ 2 \leq n \leq 2 \cdot 10^5 $
2. The graph is a tree.
3. In each operation:
- $ a_i, b_i $ are leaves of the current tree.
- $ c_i \in \{a_i, b_i\} $ is the leaf removed.
- The tree remains connected after removal.
**Objective**
Maximize the final answer:
$$
A_{n-1} = \sum_{i=1}^{n-1} d(a_i, b_i)
$$
and construct a sequence of operations $ \{(a_i, b_i, c_i)\}_{i=1}^{n-1} $ achieving this maximum.
API Response (JSON)
{
"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 l...",
"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_sp...",
"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 th...",
"is_translate": false,
"language": "Formal"
}
]
}