题目大意是给定一棵树，每次选择两个叶子将其删除，同时将两个叶子之间的简单路径长度加到答案上，找到一种方案使答案最大化，并输出删除的顺序。
首先有一个结论是，距离树上某个节点最远的节点一定是某条直径的某个端点。
证明：反证法。设树上某条直径左端点为L，右端点为R，距离当前节点x最远的点为P。如果x就在直径上，那么P到L的简单路径/P到R的简单的路径长度中较大的那个值一定大于直径的长度，与直径定义矛盾。如果x不在直径上，那么设x到L的简单路径与直径重合的第一个点为Q，此时如果x到P的简单路径与直径不重合，因为x到P更远，所以用PL或者PR替代当前直径一定更优，与直径定义矛盾；如果x到P的简单路径与直径有重合，即x到P必定经过Q，因为xP>max(xL, xR)，因此QP > max(QL, QR)，同样可知用PL或者PR替代当前直径一定更优，与直径定义矛盾。
所以，最优的方案就是先从远到近删除不在直径上的点，然后删除直径。直径可用两次dfs求出。
#include <bits/stdc++.h>
#define int long long
#define en cout<<endl;
#define de(x) cout<<x;
#define N 200005
using namespace std;
int n, head[N], ver[2 * N], Next[2 * N], tot = 0;
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
int root, root2;
int mxdep = 0;
int dep[3][N];
int fa[N];
struct node {
int a, b, c;
};
void dfs1(int x, int pre, int d) {
if(d > mxdep) {
mxdep = d;
root = x;
}
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
dfs1(y, x, d + 1);
}
}
vector<node> v;
void dfs2(int x, int pre, int d, int round) {
dep[round][x] = d;
if(round == 1) {
fa[x] = pre;
}
if(d > mxdep) {
mxdep = d;
root2 = x;
}
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
dfs2(y, x, d + 1, round);
}
}
bool link[N];
int ans = 0;
void dfs3(int x, int pre, vector<node> &v) {
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
dfs3(y, x, v);
}
if(link[x]) return;
if(dep[1][x] > dep[2][x]) {
ans += (dep[1][x] - 1);
v.push_back({x, root, x});
} else {
ans += (dep[2][x] - 1);
v.push_back({x, root2, x});
}
}
void solve() {
cin >> n;
memset(dep, 0, sizeof(dep));
memset(link, 0, sizeof(link));
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs1(1, 0, 1);
mxdep = 0;
dfs2(root, 0, 1, 1);
dfs2(root2, 0, 1, 2);
int now = root2;
vector<int> linkp;
while(now) {
link[now] = 1;
ans += (dep[1][now] - 1);
if(now != root) linkp.push_back(now);
now = fa[now];
}
vector<node> v;
dfs3(root, 0, v);
for(auto x : linkp) {
v.push_back({x, root, x});
}
cout << ans << endl;
for(auto x : v) {
cout << x.a << " " << x.b << " " << x.c << endl;
}
return;
}
signed main() {
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}