[CF911F]Tree Destruction

题目大意

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


思路

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


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
typedef long long int64;
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (num << 3) + (num << 1) + ch - '0';return sgn ? num : -num;
}
#define N 200002
int head[N],next[N << 1],to[N << 1],tot = 0;
inline void addedge(int u,int v)
{
next[++tot] = head[u];to[tot] = v;head[u] = tot;
next[++tot] = head[v];to[tot] = u;head[v] = tot;
}
bool mark[N];
int u,v,n,disu[N] = {-1},disv[N] = {-1},fa[N],seq[N];
void dfs1(int x,int f)
{
disv[x] = disv[f] + 1;
if(disv[x] > disv[u]) u = x;
for(register int i = head[x],y = to[i];~i;y = to[i = next[i]]) if(y != f) dfs1(y,x);
}
void dfs2(int x,int f)
{
fa[x] = f;seq[++seq[0]] = x;
disu[x] = disu[f] + 1;
if(disu[x] > disu[v]) v = x;
for(register int i = head[x],y = to[i];~i;y = to[i = next[i]]) if(y != f) dfs2(y,x);
}
void dfs3(int x,int f)
{
disv[x] = disv[f] + 1;
for(register int i = head[x],y = to[i];~i;y = to[i = next[i]]) if(y != f) dfs3(y,x);
}
struct answer{int a,b,c;}ans[N];
int cnt;
int main()
{
memset(head,-1,sizeof(head));
n = getint();
for(register int i = 1;i < n;i++) addedge(getint(),getint());
dfs1(1,0);dfs2(u,0);dfs3(v,0);
for(register int i = v;i;i = fa[i]) mark[i] = 1;
int64 sum = 0;
for(register int i = seq[0];i;i--)
{
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 = fa[i])
{
ans[++cnt] = (answer){u,i,i};
sum += disu[i];
}
printf("%I64d\n",sum);
for(register int i = 1;i <= cnt;i++) printf("%d %d %d\n",ans[i].a,ans[i].b,ans[i].c);
return 0;
}