CF991F「Tree Destruction」

1. 题目

题目链接:CF991F「Tree Destruction」

Description

You are given an unweighted tree with nn vertices. Then n1n - 1 following operations are applied to the tree. A single operation consists of the following steps:

  1. choose two leaves;
  2. add the length of the simple path between them to the answer;
  3. remove one of the chosen leaves from the tree.

Initial answer (before applying operations) is 00. Obviously after n1n - 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!

Input

The first line contains one integer number nn (2n21052 \leq n \leq 2 \cdot 10^5) — the number of vertices in the tree.

Next n1n - 1 lines describe the edges of the tree in form aia_i, bib_i (1ai,bin;aibi1 \leq a_i, b_i \leq n; a_i \neq b_i). It is guaranteed that given graph is a tree.

Output

In the first line print one integer number — maximal possible answer.

In the next n1n - 1 lines print the operations in order of their applying in format ai,bi,cia_i, b_i, c_i, where ai,bia_i, b_i — pair of the leaves that are chosen in the current operation (1ai,bin1 \leq a_i, b_i \leq n), cic_i (1cin,ci=aici=bi1 \leq c_i \leq n, c_i = a_i \vee c_i = b_i) — choosen leaf that is removed from the tree in the current operation.

See the examples for better understanding.

Examples

Input #1

1
2
3
3
1 2
1 3

Output #2

1
2
3
3
2 3 3
2 1 1

Input #2

1
2
3
4
5
5
1 2
1 3
2 4
2 5

Output #2

1
2
3
4
5
9
3 5 5
4 3 3
4 1 1
4 2 2

2. 题解

分析

这道题主要考察的就是求树的直径。树有一个重要的性质:假设结点 sstt 之间唯一的简单路径是树的直径,则树中任意结点的最远结点要么是 ss 要么是 tt 于是,对于这道题而言,一定是先删除非树的直径上的所有结点,然后再删除树的直径上的结点。删除非树的直径上的结点先从叶结点开始,即度为 1 的结点,可以用一个队列维护,然后删除后更新父结点的度,一旦父结点变为叶结点(即度为 1 ),则将父结点加入队列中。该题的解答步骤为:

  • 首先以任意结点 uu 为根对树进行第一遍 DFS,求出树的直径的某一端点 ss

  • 然后以 ss 为根对树进行第二遍 DFS,求出树的直径的另一端点 tt,同时记录所有结点到 ss 的简单路径长度。

  • 接着以 tt 为根对树进行第三遍 DFS,记录所有结点到 tt 的简单路径,同时记录树的直径路径。

  • 然后使用队列维护除 sstt 外的所有叶结点,逐一删除队列中的叶结点,并更新父结点的度和队列。对于每个非树的直径上的结点而言,其对答案贡献最大的值即为其到 ss 的简单路径长度与到 tt 的简单路径长度二者之中的最大值。

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#define ll int
#define MAXN 200005
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct Edge {
ll to, next;
}e[MAXN<<1];
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
e[cnt].to = u;
e[cnt].next = head[v];
head[v] = cnt++;
}

ll s, t;
ll ans;
ll idx;
ll vis[MAXN];
ll parent[MAXN];
ll depth1[MAXN], depth2[MAXN];
ll *depth;
void dfs(ll u, ll curdepth) {
vis[u] = 1;
depth[u] = curdepth;
if(depth[u] > ans) {
ans = depth[u];
idx = u;
}
for(ll i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if(!vis[v]) {
parent[v] = u;
dfs(v, curdepth+1);
}
}
}

void answer(ll u) {
// 第一次 dfs
ans = 0;
parent[u] = u;
memset(vis, 0, sizeof(vis));
depth = depth1;
dfs(u, 0);
// 第二次 dfs
ans = 0;
s = idx;
parent[idx] = idx;
memset(vis, 0, sizeof(vis));
depth = depth1;
dfs(idx, 0);
// 第三次 dfs
ans = 0;
parent[idx] = idx;
t = idx;
memset(vis, 0, sizeof(vis));
depth = depth2;
dfs(idx, 0);
}


int main()
{
ll n;
init();
scanf("%d", &n);
ll u, v;
ll in[MAXN] = {0};
for(ll i = 0; i < n-1; ++i) {
scanf("%d%d", &u, &v);
addEdge(u, v);
++in[u];
++in[v];
}
answer(u);
queue <ll> q;
for(ll i = 1; i <= n; ++i) {
if(in[i] == 1 && i != s && i != t) {
q.push(i);
}
}
long long ans = 0;
ll count = 0;
ll way[MAXN][3];
while(q.size()) {
u = q.front();
q.pop();
if(depth1[u] > depth2[u]) {
v = s;
ans += depth1[u];
} else {
v = t;
ans += depth2[u];
}
way[count][0] = v;
way[count][1] = u;
way[count][2] = u;
count++;
--in[parent[u]];
if(in[parent[u]] == 1) {
q.push(parent[u]);
}
}
u = s;
while(parent[u] != u) {
way[count][0] = t;
way[count][1] = u;
way[count][2] = u;
count++;
ans += depth2[u];
u = parent[u];
}
printf("%lld\n", ans);
for(ll i = 0; i < count; ++i) {
printf("%d %d %d\n", way[i][0], way[i][1], way[i][2]);
}
return 0;
}