# CF991F「Tree Destruction」

## 1. 题目

### Description

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 \leq n \leq 2 \cdot 10^5$) — the number of vertices in the tree.

Next $n - 1$ lines describe the edges of the tree in form $a_i$, $b_i$ ($1 \leq a_i, b_i \leq n; a_i \neq 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 \leq a_i, b_i \leq n$), $c_i$ ($1 \leq c_i \leq n, c_i = a_i \vee c_i = b_i$) — choosen leaf that is removed from the tree in the current operation.

See the examples for better understanding.

## 2. 题解

### 分析

• 首先以任意结点 $u$ 为根对树进行第一遍 DFS，求出树的直径的某一端点 $s$

• 然后以 $s$ 为根对树进行第二遍 DFS，求出树的直径的另一端点 $t$，同时记录所有结点到 $s$ 的简单路径长度。

• 接着以 $t$ 为根对树进行第三遍 DFS，记录所有结点到 $t$ 的简单路径，同时记录树的直径路径。

• 然后使用队列维护除 $s$$t$ 外的所有叶结点，逐一删除队列中的叶结点，并更新父结点的度和队列。对于每个非树的直径上的结点而言，其对答案贡献最大的值即为其到 $s$ 的简单路径长度与到 $t$ 的简单路径长度二者之中的最大值。