rt,#26应输出1228，该代码输出1155

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
vector<int> G[N];
int op,pos;
int dis[N],pre[N];
int v,u;
bool vis[N];
long long ans;
queue<pair<int,int> > q;
void dfs(int x,int fa,int now){
    if(now>op) op=now,pos=x;
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(y==fa) continue;
        dfs(y,x,now+1);
    }
}
void dfs2(int x,int fa,int now){
    dis[x]=now;
    pre[x]=fa;
    if(now>op) op=now,pos=x;
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(y==fa) continue;
        dfs2(y,x,now+1);
    }
}
void dfs3(int x,int fa){
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(dis[x]>dis[y]) continue;
        if(!vis[y]) dfs3(y,x);
        else dfs3(y,y);
    }
    if(!vis[x]){
        if(dis[x]>dis[x]+dis[v]-2*dis[fa]){
            ans+=dis[x];
            q.push({u,x});
        }
        else{
            ans+=dis[x]+dis[v]-2*dis[fa];
            q.push({v,x});
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,0);
    op=0;
    u=pos;
    dfs2(pos,0,0);
    v=pos;
    for(int i=v;i!=0;i=pre[i]) vis[i]=true;
    dfs3(u,u);
    for(int i=v;i!=u;i=pre[i]){
        ans+=dis[i];
        q.push({u,i});
    }
    printf("%lld\n",ans);
    while(!q.empty()){
        printf("%d %d %d\n",q.front().first,q.front().second,q.front().second);
        q.pop();
    }
}