CCF GESP 2025年12月认证 C++ 7级

A 国有 $n$ 座城市，城市之间由 $m$ 条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以 $1,2,…,n$ 编号。第 $i(1≤i≤m)$ 条双向道路连接城市 $u_i$ 与城市 $v_i$。

对于城市 $u$ 和城市 $v$ 而言，它们之间的连通度 $d(u,v)$ 定义为从城市 $u$ 出发到达城市 $v$ 所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足$d(u,v)=d(v,u)$，特殊地有 $d(u,u)=0$。

现在 A 国正在规划城市建设方案。城市 $u$ 的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得 $max_{1≤i≤n} d(u,i)$ 最小的 $u$，若存在多个可能的 $u$ 则选取其中最小的。

班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以 $1,2,…,n$ 编号，第 $i$ 名同学有其发言积极度 $c_i$。

观察发现，如果一个学习小组中恰好包含编号为 $p_1,p_2,...,p_k$ 的 k 名同学，则该学习小组的基础讨论积极度为 $a_k$，综合讨论积极度为 $a_k+max\{c_{p1},c_{p2},…,c_{pk}\} - min\{c_{p1},c_{p2},…,c_{pk}\}$，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。

给定基础讨论积极度 $a_1,a_2,…,a_n$，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。