CF991F「Tree Destruction」
CF991F「Tree Destruction」
1. 题目
题目链接：CF991F「Tree Destruction」 。
Description
You are given an unweighted tree with nnn vertices. Then n - 1following 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 aftern - 1such 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 nnn (2 \leq n \leq 2 \cdot 10^5) — the number of vertices in the tree.
Next n - 1lines describe the edges of the tree in form a_i, b_i (1 \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 n−1 lines print the operations in order of their applying in format a_i, b_i, c_i, where a_i, b_i— pair of the leaves that are chosen in the current operation (1 \leq a_i, b_i \leq n, c_i (1 \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 understandin
Examples
Input #1
3
1 2
1 3Output #2
3
2 3 3
2 1 1Input #2
5
1 2
1 3
2 4
2 5Output #2
9
3 5 5
4 3 3
4 1 1
4 2 22. 题解
分析
这道题主要考察的就是求树的直径。树有一个重要的性质：假设结点 s和 t 之间唯一的简单路径是树的直径，则树中任意结点的最远结点要么是 s 要么是 t 。 于是，对于这道题而言，一定是先删除非树的直径上的所有结点，然后再删除树的直径上的结点。删除非树的直径上的结点先从叶结点开始，即度为 1 的结点，可以用一个队列维护，然后删除后更新父结点的度，一旦父结点变为叶结点（即度为 1 ），则将父结点加入队列中。该题的解答步骤为：
- 首先以任意结点 u 为根对树进行第一遍 DFS，求出树的直径的某一端点 s 。
- 然后以 s为根对树进行第二遍 DFS，求出树的直径的另一端点 t，同时记录所有结点到 s 的简单路径长度。
- 接着以 t 为根对树进行第三遍 DFS，记录所有结点到 t的简单路径，同时记录树的直径路径。
- 然后使用队列维护除 s 和 t 外的所有叶结点，逐一删除队列中的叶结点，并更新父结点的度和队列。对于每个非树的直径上的结点而言，其对答案贡献最大的值即为其到 s 的简单路径长度与到 t 的简单路径长度二者之中的最大值。
代码
#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;
}