丑陋的代码：(不要在意这恐怖的5dfs)

#include<cstdio>
#include<vector>
using namespace std;
int ans;
int maxdep;
int r[200001];
int dis[200001];
int n,root1,root2;
bool diameter[200001];
vector<int> G[200001];
void dfs1(int u,int fa,int dep)
{
    if(dep>maxdep)
    {
        root1=u;
        maxdep=dep;
    }
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs1(v,u,dep+1);
        }
    }
}
void dfs2(int u,int fa,int dep)
{
    if(dep>maxdep)
    {
        root2=u;
        maxdep=dep;
    }
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs2(v,u,dep+1);
        }
    }
}
bool dfs3(int u,int fa,int dep)
{
    r[u]=root1;
    dis[u]=dep;
    if(u==root2)
    {
        diameter[u]=1;
        return 1;
    }
    bool res=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            if(dfs3(v,u,dep+1))
            {
                res=1;
                diameter[u]=1;
            }
        }
    }
    return res;
}
void dfs4(int u,int fa,int dep)
{
    if(dep>dis[u])
    {
        dis[u]=dep;
        r[u]=root2;
    }
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs4(v,u,dep+1);
        }
    }
}
void dfs5(int u,int fa)
{
    ans+=maxdep;
    maxdep--;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if((v!=fa)&&diameter[v])
        {
            printf("%d %d %d\n",u,v,u);
            dfs5(v,u);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
   dfs1(1,0,0);
   maxdep=0;
   dfs2(root1,0,0);
   dfs3(root1,0,0);
   dfs4(root2,0,0);
   for(int i=1;i<=n;i++)
   {
       if(!diameter[i])
       {
           ans+=dis[i];
       }
   }
   ans+=((1+maxdep)*maxdep)/2;
   printf("%d\n",ans);
   for(int i=1;i<=n;i++)
   {
       if(!diameter[i])
       {
           printf("%d %d %d\n",i,r[i],i);
       }
   }
   dfs5(root1,0);
}