题目大意：给出一棵树，进行n-1次操作。每次操作包括找两个点，距离加到ans中，再删除其中一个点，n-1次操作后将只剩1个点，求最大ans。

题解：先求出树的直径，两个端点为p1、p2，操作分2种。

第一种，删除非直径上的点（a、b、c），如图

                            


操作时，选择的点对为{a,max(p1,p2)},max(p1,p2)表示a到p1，p2距离最大的点，删除的点为a。

第二种，删除直径上的点

                            

操作时，从左至右依次操作相邻的两个点即可，删除最左边的点。


代码：

#include<bits/stdc++.h>
#define N 200010
#define INF 1e9
#define LL long long
using namespace std;

int d1[N],d2[N],a[N],b[N],c[N],f[N],du[N];
vector<int>G[N];
queue<int>q;
void dfs(int x,int fa,int *d)
{
    for (int i=0;i<G[x].size();i++)
    {
        int v=G[x][i];
        if (v!=fa)
        {
            d[v]=d[x]+1;
            dfs(v,x,d);
        }
    }
}

void out(int x,int fa,int p2)
{
    for(int i=0;i<G[x].size();i++)
    {
        int v=G[x][i];
        if (!f[v] && v!=fa)
        {
            printf("%d %d %d\n",x,p2,x);
            out(v,x,p2);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int j,k;
        scanf("%d%d",&j,&k);
        G[j].push_back(k);G[k].push_back(j);du[k]++,du[j]++;
    }
    int p1,p2,m=0;
    d1[1]=0;dfs(1,-1,d1);
    for (int i=1;i<=n;i++) if (m<d1[i]) { m=d1[i];p1=i;}
    d1[p1]=0;dfs(p1,-1,d1); m=0;
    for (int i=1;i<=n;i++) if (m<d1[i]) { m=d1[i];p2=i;}
    d2[p2]=0;dfs(p2,-1,d2);
    LL ans=0;m=0;
    for (int i=1;i<=n;i++) if(d1[i]+d2[i]!=d1[p2] && du[i]==1) q.push(i);
    while(!q.empty())
    {
        int i=q.front();q.pop();
        for (int u=0;u<G[i].size();u++)
        {
            int v=G[i][u];if (f[v])continue;
            ans+=max(d1[i],d2[i]);
            a[++m]=i;b[m]=d1[i]>d2[i]?p1:p2;c[m]=i;f[i]=1;
            du[v]--;
            if(du[v]==1) q.push(v);
        }
    }
    ans+=(LL) (1+d1[p2])*d1[p2]/2;
    printf("%I64d\n",ans);
    for (int i=1;i<=m;i++) printf("%d %d %d\n",a[i],b[i],c[i]);
    out(p1,-1,p2);
}