AdditionalFile4975.zip

P3596 [POI 2015 R3] 高速公路现代化 Highway modernization

题目描述

给定一棵无根树，边权都是 $1$，请去掉一条边并加上一条新边，定义直径为最远的两个点的距离，请输出所有可能的新树的直径的最小值和最大值。

输入格式

第一行包含一个正整数 $n$，表示这棵树的点数。
接下来 $n-1$ 行，每行包含两个正整数，表示 $u,v$ 之间有一条边。

输出格式

第一行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$表示新树直径的最小值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。

第二行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$ 表示新树直径的最大值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。若有多组最优解，输出任意一组。

输入输出样例 #1

输入 #1

6
1 2
2 3
2 4
4 5
6 5

输出 #1

3 4 2 2 5
5 2 1 1 6

说明/提示

【数据范围】

对于 $100\%$ 的数据，$2 \le n \le 5 \times 10 ^ 5$。

原题名称：Modernizacja autostrady。

感谢 @cn：苏卿念 提供 spj

#4975. 「POI2015 R3」高速公路现代化 Highway modernization

标签: 传统 | 时间限制: 11000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Modernizacja autostrady

字节城有 $n$ 座城市，连接它们的道路网络密集但老旧，因此近年新建了 $n-1$ 条现代化高速公路，确保任意两城可通过高速公路直达。然而，高速公路收费高昂，引发市民不满。交通部长决定优化高速公路网，平息民怨。年度预算仅允许拆除一条高速公路并新建一条（可能在原位置但更现代化）。他希望选择拆建方案，保证任意两城仍可通过高速公路连通，且两城间最长路径上的高速公路数尽可能少，称为乐观方案。

与此同时，财政部长希望通过现代化提升收费收入，目标是保证连通性，但使两城间最长路径的高速公路数尽可能多，称为悲观方案。

两位部长的计划传到媒体，记者 Bajtazar 正撰写相关报道，需展示最乐观和最悲观的现代化方案。请你编写程序，为他的文章提供准确数据。

输入格式

第一行包含一个整数 $n$ $(3 \leq n \leq 500000)$，表示字节城城市数量，城市编号为 $1$ 到 $n$。

接下来的 $n-1$ 行描述高速公路，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示 $a_i$ 号和 $b_i$ 号城市间有高速公路。

输出格式

第一行包含五个整数 $k, x_1, y_1, x_2, y_2$，描述乐观方案：两城间最长路径的高速公路数为 $k$，拆除 $x_1$ 和 $y_1$ 间的高速公路，建设 $x_2$ 和 $y_2$ 间的高速公路。

第二行以相同格式描述悲观方案。拆建城市对可任意排序。若有多种方案，输出任意一种。

程序需输出两行，每行答案独立评分。若仅一个方案正确，得测试点一半分数，此时另一行内容不影响评分。

样例

输入

6
1 2
2 3
2 4
4 5
6 5

输出

3 4 2 2 5
5 2 1 1 6

• 乐观方案：拆除 $4$ 和 $2$ 间高速公路，建设 $2$ 和 $5$ 间高速公路，最长路径高速公路数为 $3$。
• 悲观方案：拆除 $2$ 和 $1$ 间高速公路，建设 $1$ 和 $6$ 间高速公路，最长路径高速公路数为 $5$。

附加样例

1. $n=5$，星型网络；
2. $n=1000$，链型网络；
3. $n=2^{18}$，每座城市 $i>1$ 通过高速公路连接到城市 $\lfloor \frac{i}{2} \rfloor$。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000$。