题意：
给你一棵 \(n\) 个结点组成的树，你需要对树进行 \(n-1\) 次操作，一次操作包含如下的步骤：
- 选择两个叶子结点
- 将这两个结点之间简单路径的长度加到答案中
- 从树上删去两个叶子结点之一
初始答案为 \(0\)，显然在 \(n-1\) 次操作之后树上只剩下一个结点。
计算最大的答案，并构造一组操作序列。
思路：
构造题……向来是我不拿手的。
浅析一下本人的思考过程。一开始想的是根据结点的深度进行构造，统计出每个深度的结点个数，然后枚举最大和次大的两个深度组合出最长的路径，优先割掉个数较少的深度的点。似乎可以统计出答案，但问题在于你并不知道其中的某两个结点是不是在同一棵子树内，也就不能通过直接计算深度来求两点距离。如果加lca，时间复杂度又炸了。。。
那换一个思路，在一棵树上，且是一条距离最大的路径，似乎与树的直径有关系？
先回顾一下树的直径的一些性质：
- 对任一一个点来说，与它距离最远的点一定是树的直径的某个端点。
- 对于两棵树，如果第一棵树的直径的两端点为 \((x,y)\)，第二棵树的直径的两端点为 \((u,v)\)，那么将两棵树连起来，新树的直径的两个端点一定是四个点中的其中两个点。
- 对于一棵树，增删一个叶子结点，最多改变直径的一个端点。
- 如果一棵树有多条直径，那么所有直径必交于一点。
- 任一两条直径一定有且仅有一个极长连续段重合。
对于这道题来说，第一个性质是最重要的。它为方案的构造指明了思路。
可以先两遍 \(dfs\) 找出树的一条直径，然后将所有不在直径上的点与与它距离最远的一个直径的端点配对，再把这个点删除。
对于在直径上的点，等把所有不在直径上的点全部删除后，再挨个删掉即可。
这里有个细节，当你在处理没在直径上的点，求哪个端点与与它最远时，还要记录一下这个没在直径上的点和另一个端点的lca，这样才能求距离。算是一个比较有用的技巧吧，在代码里会展示。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5;
int n,pos[MAXN + 5][2],dp[MAXN + 5][2],tot,head[MAXN + 5],dep[MAXN + 5],S,T,ans;
bool od[MAXN + 5];//是否在直径上
vector<pair<int,int> > out;
struct EDGE{
int u,v,next;
}edge[2 * MAXN + 5];
void add(int u,int v){
++tot;
edge[tot] = (EDGE){u,v,head[u]};
head[u] = tot;
}
void dfs(int u){//求直径
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(dep[v] < dep[u])continue;
dep[v] = dep[u] + 1;
dfs(v);
}
}
void dfs1(int u){
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(dep[v] > dep[u]){
dfs1(v);
od[u] = od[u] || od[v];//标记是否在直径上
}
}
}
void dfs2(int u,int root){
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(dep[v] > dep[u])dfs2(v,(od[v] ? v : root));//如果访问到深度较当前更大的点（即父结点），假如这个点是在直径上的，那么之后从这个点出发的、不在直径上的点与直径的其中一个端点的lca就深了一层；如果不在直径上，则对lca无影响。（可以画个图想一想）
}
if(!od[u]){
if(dep[u] > dep[u] + dep[T]-(dep[root]<<1)){//比较到两个端点的距离
ans += dep[u];
out.push_back(make_pair(S,u));
}
else{
ans += dep[u] + dep[T] - (dep[root]<<1);
out.push_back(make_pair(T,u));
}
}
}
signed main(){
scanf("%lld",&n);
for(int i = 1; i < n; i++){
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
memset(dep,0x3f,sizeof dep);
dep[1] = 0;
S = 1;
dfs(S);
for(int i = 2; i <= n; i++){
if(dep[i] > dep[S])S = i;
}
memset(dep,0x3f,sizeof dep);
dep[S] = 0;
T = S;
dfs(S);
for(int i = 1; i <= n; i++){
if(dep[i] > dep[T])T = i;
}
od[T] = 1;
dfs1(S);
dfs2(S,S);
int now = T;
while(now != S){
ans += dep[now];
for(int i = head[now]; i; i = edge[i].next){
int v = edge[i].v;
if(od[v] && dep[v] < dep[now]){
out.push_back(make_pair(S,now));
now = v;
break;
}
}
}
cout << ans << "\n";
for(int i = 0; i < out.size(); i++){
cout << out[i].first << " " << out[i].second << " " << out[i].second << "\n";
}
}