[CF911F]Tree Destruction

题目大意：
　　给你一棵树，每次选取其中的两个叶子结点，往答案中加上它们的距离，并删去其中一个结点。
　　你可以自由进行上述操作，使得最后答案最大。
　　问答案最大是多少，并输出其中一种方案。

思路：
　　贪心。
　　首先找出树的直径，然后枚举直径外的叶子结点。
　　看一下该结点到直径两端距离哪个长，并加上这个距离。
　　删去这个点。
　　最后按顺序删直径上的点。
　　每次存一下方案，最后直接输出即可。

#include<cstdio>
#include<cctype>
#include<vector>
typedef long long int64;
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=200001;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
    e[u].push_back(v);
    e[v].push_back(u);
}
bool mark[N];
int u,v,disu[N]={-1},disv[N]={-1},from[N],seq[N];
void dfs1(const int &x,const int &par) {
    disv[x]=disv[par]+1;
    if(disv[x]>disv[u]) u=x;
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i];
        if(y==par) continue;
        dfs1(y,x);
    }
}
void dfs2(const int &x,const int &par) {
    from[x]=par;
    seq[++seq[0]]=x;
    disu[x]=disu[par]+1;
    if(disu[x]>disu[v]) v=x;
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i];
        if(y==par) continue;
        dfs2(y,x);
    }
}
void dfs3(const int &x,const int &par) {
    disv[x]=disv[par]+1;
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i];
        if(y==par) continue;
        dfs3(y,x);
    }
}
struct Answer {
    int a,b,c;
};
Answer ans[N];
int cnt;
int main() {
    const int n=getint();
    for(register int i=1;i<n;i++) {
        add_edge(getint(),getint());
    }
    dfs1(1,0);
    dfs2(u,0);
    dfs3(v,0);
    for(register int i=v;i;i=from[i]) mark[i]=true;
    int64 sum=0;
    for(register int i=seq[0];i;i--) {
        const int x=seq[i];
        if(mark[x]) continue;
        if(disu[x]>disv[x]) {
            ans[cnt++]=(Answer){u,x,x};
            sum+=disu[x];
        } else {
            ans[cnt++]=(Answer){v,x,x};
            sum+=disv[x];
        }
    }
    for(register int i=v;i!=u;i=from[i]) {
        ans[cnt++]=(Answer){u,i,i};
        sum+=disu[i];
    }
    printf("%I64d
",sum);
    for(register int i=0;i<cnt;i++) {
        printf("%d %d %d
",ans[i].a,ans[i].b,ans[i].c);
    }
    return 0;
}