CF911F Tree Destruction

给定一棵有 $n$ 个顶点的无权树。然后对这棵树依次进行 $n-1$ 次操作。每次操作包括以下步骤： 1. 选择树上的两个叶子节点； 2. 将这两个叶子间简单路径的长度加到当前答案中； 3. 从树中移除选中的其中一个叶子节点。 初始答案为 $0$。显然，经过 $n-1$ 次这样的操作后，树中只剩下一个顶点。 请计算你能获得的最大答案，并构造一种操作顺序，使你能获得这个最大答案！

第一行包含一个整数 $n$（$2\le n\le 2\cdot10^{5}$）——树的顶点数。 接下来的 $n-1$ 行描述树的边，每行用形式 $a_i,b_i$ 给出一条边（$1\le a_i, b_i\le n$，$a_i\ne b_i$）。保证给出的图是一棵树。

第一行输出一个整数——你能获得的最大答案。 接下来 $n-1$ 行，按操作顺序输出每次操作，格式为 $a_i,b_i,c_i$，其中 $a_i,b_i$ 表示本次操作所选择的两个叶子结点（$1\le a_i, b_i\le n$），$c_i$（$1\le c_i\le n$，$c_i=a_i$ 或 $c_i=b_i$）表示本次操作中被从树中移除的叶子。 具体见样例。

由 ChatGPT 5 翻译