CF1805

D

我直接猜测，设某条直径端点为 \(u,v\)，对于一个 \(k\) 只需要合并 \(u\) 和距离 \(\ge k\) 的点，\(v\) 和距离 \(\ge k\) 的点即可。

证明，首先 \(k\le\) 直径长度，否则答案为 \(n\)。

这样 \(u,v\) 在一个连通块内，设这个连通块为 \(T\)。试图证明，一个点要么在 \(T\) 内要么自己独立一个连通块。

考虑若存在 \(x,y\) 不同时在 \(T\) 内，满足 \(dis(x,y)\ge k\)，则有 \(x\) 到 \(u,v\) 其一的 \(dis\) 也 \(\ge k\)，\(y\) 到 \(u,v\) 其一的 \(dis\) 也 \(\ge k\)（直径的性质）。此时 \(x,y\) 都在 \(T\) 内，矛盾。

从大到小处理 \(k\)，复杂度 \(\Theta(n)\)。

E

典题啊，以后看到一定要想起来啊。考虑某种颜色的全局出现次数：

• 如果为 \(1\)，则不对任何边有贡献。

• 如果为 \(2\)，则只对路径上的边有贡献。

• 如果为 \(3\)，则对所有边有贡献。

离线处理路径取 \(\max\) 即可，复杂度 \(\Theta(n\log n)\)。

F

easy version 是 \(n\le 3000\)。

这部分有一个显然的暴力，对 \(a\) 排序，维护每一层得到的序列，每次可以优先队列 \(\Theta(n\log n)\) 求下一层。

有一个问题，这样每过一层值域翻倍，到后面就维护不了了。

观察发现每一层的极差不升，因为第一项必定是 \(a_1+a_2\)，最后一项小于等于 \(a_1+a_k\)，\(k\) 是上一层长度。

那我们可以每次求完令 \(a_i\gets a_i-a_1\)，令答案加上这个最小值对之后的影响，即 \(a_12^{n-c}\)，\(c\) 是轮数。

这样就可以 \(\Theta(n^2\log n)\) 通过 easy version。

考虑 \(n\le2\times10^5\)。注意到我们只希望求最后的 \(a_1\)，不一定要维护整个序列。

设阈值 \(B\)，试图只维护序列的 \(a_1\sim a_B\) 项。（操作后 \(a_1=0\)）

发现若 \(a_2+a_3\le a_B\)，\(a_{B+1}\) 之后的数不可能出现在新的 \(a'_{1\sim B}\) 中，因为已经存在一个填满 \(a'_{1\sim B}\) 的方案：

• \(a'_{1}=a_1+a_2,a'_{2}=a_1+a_3,\dots,a'_{B-1}=a_1+a_B,a'_B=a_2+a_3\)

（可能要再排序）

且任何包含 \(a_{B+1}\) 之后的数的方案都不如当前这个方案，因为它们都大于等于此方案中的最大值 \(a_1+a_B\)。

因此可以只用 \(a_{1\sim B}\) 中的数求得新的 \(a'_{1\sim B}\)，满足我们的需求。

如果 \(a_2+a_3>a_B\) 呢？

由于每次操作完要减去最小值，直觉上操作后最大值会减半。具体而言：

我们进行两次求解，发现每次求解会导致最后一个数可能包含 \(a_{B+1}\) 之后的数，前面位置都可以只依靠 \(a_{1\sim B}\) 求出。

我们直接这样的每次求解舍弃维护新的 \(a'_B\)，并令 \(B\gets B-1\)。

严谨地，操作一次后的序列 \(a'\) 的最大值 \(a'_{B-1}\) 小于等于 \(a_B\)。进行减去最小值的操作后小于等于 \(a_B-a_2\)。

操作两次后的序列 \(a''\) 的最大值 \(a''_{B-2}\le a'_{B-1}\le a_B-a_2\)。

进行减去最小值的操作后 \(\le a_B-a_2-(a_3-a_2)=a_B-a_3<\frac12a_B\)。

这说明第二种情况不会出现超过 \(\log V\) 次，每次需要舍弃维护 \(2\) 个末尾的数。

即，直接令 \(B=2\log n+1\) 即可保证最后能维护到 \(a_1\)。

复杂度 \(\Theta(nB\log B)=\Theta(n\log V\log\log V)\)。