问题描述
You are given an unweighted tree with n vertices. Then n - 1 following operations are applied to the tree. A single operation consists of the following steps:
- choose two leaves;
- add the length of the simple path between them to the answer;
- remove one of the chosen leaves from the tree.
Initial answer (before applying operations) is 0. Obviously after n - 1 such operations the tree will consist of a single vertex.
Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!
输入格式
The first line contains one integer number n (2 ≤ n ≤ 2·105) — the number of vertices in the tree.
Next n - 1 lines describe the edges of the tree in form ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). It is guaranteed that given graph is a tree.
输出格式
In the first line print one integer number — maximal possible answer.
In the next n - 1 lines print the operations in order of their applying in format ai, bi, ci, where ai, bi — pair of the leaves that are chosen in the current operation (1 ≤ ai, bi ≤ n), ci (1 ≤ ci ≤ n, ci = ai or ci = bi) — choosen leaf that is removed from the tree in the current operation.
See the examples for better understanding.
样例输入
3
1 2
1 3
样例输出
3
2 3 3
2 1 1
解析
首先我们要知道一个性质：无权树上任意一个节点，与它距离最远的节点一定是直径的某个端点。所以，利用贪心的思想，每次对一个叶节点都是用直径的两个端点离它最远的点计算答案，并且删掉当前叶节点。当只剩下直径的时候，就一个一个删点知道剩下最后一个点。
代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
#define N 200002
using namespace std;
queue<int> q;
int head[N],ver[N*2],nxt[N*2],l;
int n,i,dis1[N],dis2[N],a,b,maxx,son[N],fa[N],ans[N][3],cnt;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert(int x,int y)
{
l++;
ver[l]=y;
nxt[l]=head[x];
head[x]=l;
son[x]++;
}
void dfs(int x,int pre,int d)
{
if(d>maxx) maxx=d,a=x;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y!=pre) dfs(y,x,d+1);
}
if(son[x]==1) q.push(x);
}
void dfs1(int x,int pre)
{
if(dis1[x]>maxx) maxx=dis1[x],b=x;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y!=pre){
fa[y]=x;
dis1[y]=dis1[x]+1;
dfs1(y,x);
}
}
}
void dfs2(int x,int pre)
{
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y!=pre){
dis2[y]=dis2[x]+1;
dfs2(y,x);
}
}
}
signed main()
{
n=read();
for(i=1;i<n;i++){
int u=read(),v=read();
insert(u,v);
insert(v,u);
}
dfs(1,0,0);
maxx=0;
dfs1(a,0);
dfs2(b,0);
int sum=0,d=dis1[b];
while(!q.empty()){
while(q.front()==a||q.front()==b) q.pop();
if(q.empty()) break;
int x=q.front();
q.pop();
sum+=max(dis1[x],dis2[x]);
son[x]--;
for(i=head[x];i;i=nxt[i]){
son[ver[i]]--;
if(son[ver[i]]==1) q.push(ver[i]);
}
cnt++;
ans[cnt][0]=ans[cnt][2]=x;
if(dis1[x]>dis2[x]) ans[cnt][1]=a;
else ans[cnt][1]=b;
}
while(b!=a){
cnt++;
ans[cnt][0]=a;ans[cnt][1]=b;ans[cnt][2]=b;
b=fa[b];
sum+=d;
d--;
}
printf("%lld\n",sum);
for(i=1;i<=cnt;i++) printf("%lld %lld %lld\n",ans[i][0],ans[i][1],ans[i][2]);
return 0;
}
总结
这里有一个很好的性质值得记忆。