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$）表示本次操作中被从树中移除的叶子。

具体见样例。

输入输出样例 #1

输入 #1

3
1 2
1 3

输出 #1

3
2 3 3
2 1 1

输入输出样例 #2

输入 #2

5
1 2
1 3
2 4
2 5

输出 #2

9
3 5 5
4 3 3
4 1 1
4 2 2

说明/提示

由 ChatGPT 5 翻译