9 月做题记录
Skeleton_Huo
·
·
个人记录
R14
T1
略。
T2
通过一些观察，我们发现操作序列一定形如 C P C P P P C P P ...。
我们将每一段长度记为 a_i，有 k 段，则字符串长度为 \prod_i{a_i}，花费为 \sum_i{a_i}。
我们需要在满足 \prod_i{a_i} \ge N 的前提下，最小化 \sum_i{a_i}。
根据均值不等式，a_i 一定越平均越好，我们也可以用调整法证明：a = \{t,t,\dots,t+1,t+1,\dots\}。
注意到 k \le \log N，直接枚举。t 和 t+1 的分界点也可以直接枚举。然后二分出 t 的值。
总 O(\log^3 N \log\log N)。
T3
首先染色容易想到倒着做，这样变化会少不少。
然后区间 DP，不过显然我们只需关心区间长度，于是 f_{i,j,0/1} 表示使用到倒数第 i 个颜色，区间长度为 j，终点位于左/右端点的方案数。
可以更新到 f_{k,x,0/1}，其中颜色 [k+1,i-1] 在 j 内部跳，k 跳出去。转移可以考虑用 g_{k,x} 表示否能转移到，套一层 DP 计算即可。
T4
我们设 f_i 为经过节点 i 的路径个数。显然 ANS \ge \max{f_i}。
我们经过手玩和大胆猜想，试图证明可以取等。
考虑归纳构造的套路。如果我们能选出一个集合，使得 \max{f_i} 减 1，那么我们就完成了证明与构造。
显然选择方法就是选择若干无交路径，覆盖所有 f = \max{f_i} 的点。再具体一点，我们每次选择 f 最大的最浅点 u，并选择以其为 LCA 的路径。这样的路径总是存在的，否则 u 的父亲会是更浅的符合要求的点。该过程可以用树剖 + 线段树加速。
R15
T1
数数问题，考虑清楚方案的生成方式就不难。
T2
神秘构造题。
考虑最大效用的发挥每条线的作用。当一条线满足 (\Delta x, \Delta y) = 1 时，该线在每列都能覆盖 2 格。
于是第一步连 (0,0) 与 (n, n-1)，往下每次两端点移动两个就能高效覆盖下半部分。
上半部分是对称的，我们可能会先考虑连 (0,0) 和 (n-1,n)。但由于最后边缘部分会有漏的，要用额外两条线补充，所以这样构造可能 \lceil (n-1)/2 \rceil + \lceil (n-1)/2 \rceil + 2 > n + 1。
所以我们先连 (0,1) 和 (n-2,n)，这样就没问题了，\lceil (n-1)/2 \rceil + \lceil (n-2)/2 \rceil + 2 \le n + 1。
T3
神秘计算几何 + 数数。
首先凸多边形的面积计算可以拆成三角形，我们需要锚定一个点，注意这个点是任意的，并不一定要是给定点中的，明白这一点才会有后面灵活的贡献拆解。
要注意边的方向问题，我们规定边一律指向顺时针方向，然后可以用原点到边两端点的叉积判断正负。
于是我们发现一条边对应一个三角形，依次考虑每条边的贡献，O(n^4) 地枚举所有边，考虑它在多少个 p 中出现，可以 O(n) 解决。
T4
神秘贪心 + 推式子 + DS。
把 0 变成 -1 以变成前缀和问题。
先考虑解决单次查询的静态问题。我们有一个贪心解法：
- 从左到右依次选数，如果某次选数会使得前缀和 < 0，删除该数。
- 在已经得到的序列上倒着如是做一遍。
其正确性是显然的，最优性的证明也不难。
用 a_i 表示前缀和，b_i 表示后缀和。因为这个问题有多次查询和修改，我们需要看看有没有从这两个数组出发简便得到答案的方法。
OBS 1：第一次删除的个数为 \max_i -a_i。
每次删除都相当于 a 的后缀 +1，通过一定手模不难看出。
令第一次删除后的后缀和为 b'_i，则第二次删除个数为 \max_i -b'_i。
OBS 2：b'_i = b_i + \max_{j=1}^{n}\{-a_j\} - \max_{j=1}^{i-1}\{-a_j\}。
注意删除的都是 -1，所以是显然的。
一共删除 \max_{i=1}^n\{-a_i\} + \max_{i=1}^n\{-b'_i\} = -\min_{1 \le i < j \le n}\{a_i + b_j\}。
这里需要一些 \max 运算技巧，与 \sum 类似。
我们容易看出这其实是一个最大子段和。
证明：P10334 [UESTCPC 2024] 饮料
神秘贪心题，至今不会证。
P10875 [COTS 2022] 游戏 M
连通性相关。
P10680 [COTS 2024] 双双决斗 Dvoboj
根号分治，小块分治数组，大块递归。
AT_arc201_c [ARC201C] Prefix Covering
字符串优先考虑 Trie。
AT_arc201_b [ARC201B] Binary Knapsack
神秘贪心题，考虑奇偶性。
若 W 为奇数，不妨先选择一个价值最大的 X=0 的物品，然后把 W 减 1。
于是 X=0 的物品只能选偶数个，我们可以贪心的两两合并成 X=1 的物品，如果剩下单个就舍弃。
此时 W 和所有物品的重量都是偶数，可以全部除以 2。
AT_arc203_c [ARC203C] Destruction of Walls
比较复杂的数数题。有一定的转化和巧思。
自己做的时候把路径长 = H + W 的情况漏了。
https://www.luogu.com.cn/article/zvf63hbo
难：AT_arc202_c [ARC202C] Repunits
神秘数学题。
用到 min-max 容斥和莫比乌斯反演，还有一点和式手法。
https://www.luogu.com.cn/article/w2d98cnb
AT_arc197_c [ARC197C] Removal of Multiples
观察到删除并不会使数过于稀疏，所以可以直接暴力线段树。
严谨点的说法是质数 p 一定在 A_i = p 的时候被删除，所以至少大约第 Q 个质数还留着，线段树开到 3e6。
AT_abc209_e [ABC209E] Shiritori
字符串双端作点，字符串作边。注意不要用字符串作点，不然边数很多，而且不是标准的有向图游戏。
初始时无出边的点必败。在删点过程中，没有被标记为必胜，但无出边的点也必败。
然后将确定状态的点删去，为什么？
- 如果必败，其前驱必胜，该打的标记都打完了，留在图中没有用。
- 如果必胜，其前驱一定会避免走到该点，其存在与否不会影响前驱的必胜与必败。
最后未删的点是平局的，因为每个点在原图都没有必败后继（否则它就是必胜的，会被删去），且它不会走到原图的必胜后继，否则就输了。然后此时没有无出边的点，所以会永远周旋。
难：AT_arc165_f [ARC165F] Make Adjacent
先考虑局部，对于两个数字，有 aabb、abab、abba 三种情况。其中前两种都是变成 aabb 最优，后一种随意，操作次数的下限分别是 0, 1, 2。
我们可以证明，存在方案使得对于每一对数字都能取到下限。
解释：我们每次操作只会影响到两个数字间的相对关系，所以这里的下限是影响了两个数字间相对关系的操作次数。显然总下线就是任意两个数字的下限和。（要理解清楚需要灵活的视角，主体是一个机械的过程，这个过程中会不连续地对不同数对间的操作代价产生贡献）
若 R_a < R_b 且 L_a < L_b，则连边 a \rightarrow b，求字典序最小的拓扑序。
这样边数是 O(n^2) 的，由于是二维偏序，所以可以用 CDQ 优化建图或者主席树优化建图（不会）。
难： AT_arc199_c [ARC199C] Circular Tree Embedding
**OBS**：随意钦定一个根节点，$(T,P)$ 合法当且仅当 $T$ 的任意子树在 $P$ 上是连续的（环的意义下）。
证明不难，必要性可以看出，充分性可以归纳考虑。
对元素做映射，使得 $P^1 = 0, 1, \dots, n$。这样区间就和值域吻合了，后面更加方便。
令 $f_{l,r}$ 表示 $P^1$ 的 $[l,r]$ 区间的树的个数。
转移考虑以 $mid$ 为根，左右是区间构成的森林，用 $g_{l,r}$ 表示。
$$
f_{l,r} = \sum_{mid}{g_{l,mid-1} g_{mid+1,r}}
$$
考虑到还有其他排列的限制，我们预处理值域 $[l,r]$，是否在所有区间上都是连续的。它只用于判断 $f_{l,r}$ 是否是 $0$，因为这无法通过方程直接算出。
其他排列的限制看起来存在感有点低，但确实如此。
### 好：CF1628D2 Game on Sum (Hard Version)
博弈论 DP + DP 优化。
首先博弈论 DP **一定**画出决策树，这样十分清晰。
设 $f_{i,j}$ 表示 $i$ 次减法，$j$ 次加法的最终得分。
$$
f_{i,j} = \max_k{\min(f_{i-1,j}-k, f_{i,j-1}+k)}
$$
画出 $\min(f_{i-1,j}-k, f_{i,j-1}+k)$ 关于 $k$ 的图象，发现十分优美。
得到
$$
f_{i,j} = (f_{i-1,j} + f_{i,j-1}) / 2
$$
通过一定展开，发现可以把贡献拆开计算，答案跟路径计数有关。
**小结**：很久没见过跟函数图像有关的 DP 优化了，还是要多尝试。
### 难：CF843D Dynamic Shortest Path
**我们为什么构建 Johnson 图？**
因为在这个图上的最短路都是 $0$。
每次给 $c$ 条边加权，最短路至多增加 $c$。这样我们就可以不用 `priority_queue` 而是用桶来实现 Dijkstra，使得总复杂度降一个 $\log$。
**我陷入了什么误区？**
我以为 Johnson 图中选取的势能是增加完 $c$ 条边的边权后的 $dis$。但这样显然是无法直接得到的（不然我不就直接找到最短路了吗？）。
事实上我们选取的 $dis$ 是加权前的。
**这个误区的根本是什么？**
Johnson 图只要求一个**图**和一个**势能**即可。对于图和势能的关系没有任何要求，而我误以为势能一定要选择图的最短路。
放到这里，我们用的是加权后的图和加权前的 $dis$ 构成 Johnson 图。**加权的过程不改变势能**。
**怎么避免？**
1. 理解清楚势能与图的关系。
2. 一步一步了解我们需要做什么。
### 难：CF1163F Indecisive Taxi Fee
**代码较难**
我们有四种情况：
1. 改小，边在最短路。直接减。
2. 改小，边不在最短路。全最短路和过边最短路取 $\min$。
3. 改大，边不在最短路。不用管。
4. 改大，边在最短路。最复杂，展开讨论。
首先我们能想到如果不是最短路必经边，并不会影响答案。但仍避免不了必经边的 case。所以我们不用管必经与否。
朴素的想法是处理出删去每一条最短路上的边后的最短路。最短路有多条，但**钦定一条**比较方便解决问题，记为 $P$。
我们得到一个线性结构（最短路），考虑维护一个线性 DS 解决这个问题，线段树即可做到。
具体地，我们对于每个点 $u$，记录 $L_u$ 为 $1$ 到 $u$ 的最短路与 $P$ 的公共前缀的最右端的边的编号。这里的两条最短路在**同一个**最短路树上，也就是没有构成环。$R_u$ 与之对称。
为了方便，我们用 $L_e, R_e, e = (u,v)$ 分别表示 $L_u, R_v$。
我们枚举每条边 $(u,v)$，对 $P$ 中 $L_u$ 到 $R_v$ 之间的边进行 checkmin。整理成数据结构题，可以用吉司机树在线做，或者普通线段树离线做（从大到小枚举避免 checkmin），或者 `multiset` 离线做（扫描线）。
**这样为什么是对的？**
我们只需证明：对于任何一个 $P$ 上的边 $e$ 和 $e$ 的删边最短路在 $P$ 之外的部分 $Q$，存在 $e' \in Q$ 更新了 $e$。
假设所有的 $e' \in Q$ 都没有更新 $e$，则在 $Q$ 上一定存在一对相邻的边 $f, g$，$R_f$ 与 $L_g$ 在 $P$ 上构成的区间包含了 $e$。
我们记 $f,g$ 用于更新的最短路分别为 $d_f, d_g$，我们可以调整一下两条最短路使得 $d_f + d_g > d'_f + d'_g$，则至少有 $d_f > d'_f$ 或 $d_g > d'_g$。矛盾。
**关于求 $L,R$**：
求最短路树即可。注意倒着的时候要固定 $P$ 那一部分。
### P3530 [POI 2012] FES-Festival
**考虑极端情况是分析问题的一般方法**。我们考虑 DAG 和 SCC 的情况。
**对于 DAG**：显然解在数轴上可以无限拉长，只要按字典序排列。所以答案就是点数。
**对于 SCC**：显然变量两两之间的差值都有了上下界。
**OBS**：这个图是很紧凑的，边权都是 $0,1,-1$，所以对于任何一个解，变量的数轴上的分布都是连续的。
现在我们的任务变成了，最大化两个变量之间的差值。
任意两个变量之间的差值的**最大值**是它们之间的**最短路**，这是一个经典结论。
于是我们的答案就是任意两点最短路的最大值，还要 $+1$，因为要算上起点的 $0$。
**一般图**：答案就是所有 SCC 的答案加起来，因为 SCC 由 DAG 连接，区间之间可以被扯得无限长。
### AT_abc345_f [ABC345F] Many Lamps
首先奇数无解。
**My solution**：首先观察到我们只需要找一棵生成树即可，因为非树边是可以通过树上路径平替的，另外还发现我们可以改变树上任意两点的状态。然后按照 DFS 序构造，一次点亮一个儿子和父亲。可能会在叶子上遇到孤立点，我们记下来等 DFS 到一个不亮的点再一起点亮。
**Other solution**：我们每次操作都是让亮的灯数 $+2,0,-2$。用**中值定理**的思想，$0$ 到 $maxk$ 的所有值我们都是可以构造出来的。还是找生成树，具体的构造方法 DFS 从子树开始构造，每次都操作当前点和一个儿子，保证儿子都点亮。
这种中值定理的思想比较重要。
### 典：CF888G Xor-MST
首先建 Trie。
**Kruskal 做法**：观察到对于 Trie 上的两棵子树间连边显然不如子树内连边优，但要求连通，所以只要有一条。于是可以递归连边，连跨子树边的时候用启发式合并或者直接合并都行（因为树高有限），合并的时候贪心走 Trie。
**Boruvka 做法**：求一个块的最小边的时候先把块内的点从 Trie 上删掉，然后对每个点贪心走 Trie，最后加回来即可。
### 难：CF2041N Railway Construction
[最小生成树经典结论](https://www.luogu.com.cn/article/gq5jnvm8)
囊的过分的一道题（
考虑根号分治。
**Tips**：
1. 认为 $n$ 与 $m$ 同阶。
2. 由于禁用边和完全图的性质，本题复杂度分析有大量均摊。
**先算静态问题**：
将点按 $a$ 排序，先进行一轮魔改 Boruvka。前 $B$ 个点不连安全边，后面的点只连前 $B$ 个点。
具体地，类似 $mex$，只有前面若干个禁用边连续的时候才会起效，于是我们判断当前点的第 $i$ 条禁用边是否连向 $i$ 即可。
这样会形成若干**菊花图**和若干**单点**。菊花图中，前 $B$ 个点作花心。单点数为 $m / B$。$m + m/B > 2\sqrt m$，$B = \sqrt m$ 取最小。
故总块数 $O(\sqrt m)$。
处理出两两块之间的最小边，跑不带堆优化的 Prim 就完成了。
具体地，我们记块 $p, q$ 之间的边数为 $m_{p,q}$，由完全图的性质，我们要尽量选择 $p$ 中小的点去连 $q$ 中**最小能连**的点，而这些禁用边至多 ban 掉 $p$ 中前 $m_{p,q}$ 个点，我们扫描前 $m_{p,q}+1$ 个点即可。总复杂度是 $O(m)$ 的。
关于怎么求最小能连的边，既然有了根号，不妨大胆些。用一个 `vector` 存下任意两个块之间的边。然后枚举每一对块，利用边现场建新图，然后用上面的方法即可。
复杂度 $O(n)$。
**动态问题**：
如果删去的是 MST 上的叶子，显然是容易的。
而非叶子个数为 $O(\sqrt n)$，原本的花心，加上 Prim 每步至多产生 $2$ 个非叶子。
所以如果删非叶子，直接重跑 MST。
总复杂度 $O(n\sqrt n)$。
**无解情况（图不连通）**：
1. $n=2$ 直接输出两个 $0$。
2. 只有一个孤立点，则除删该点外，其他都是 $-1$。
3. 否则所有都是 $-1$。
**小结**：
根号方法其实是万用的，它能让很多暴力具有优秀的复杂度，又不过分依赖题目的性质，不妨多多尝试。
**代码细节**：
非常非常多。这里仅列出现 TLE 后的问题。
1. `t` 不能太小，否则 `m` 过小的时候就会有问题，可以取 `max(n,m)`。
2. 清除 `f` 的过程忘了以 `cnt` 为上限，导致复杂度假了。这启示我们对于从代码不能明显看出复杂度的题，要用一个计数器来检测一下计算量。
3. `define int long long` 的常数有点大，卡常时要关掉。
[code](https://codeforces.com/contest/2041/submission/339445616)
### AT_abc424_f Adding Chords
赛场上想到了 Hash 做法，可惜太颓了不想写。
首先断环成链，这一步无需任何代价。考虑给边的两端打赏正负标记，查询时只需求区间和就能判断是否有交。
刚开始想用 $1$ 和 $-1$，但显然不同边会相互影响，为了去除影响，我们给每个点赋随机权值（或者 $2^i \bmod P$），就解决了。
这很像某和哈希。
（哈希就是给结构赋值）
### AT_arc206_d LIS ∩ LDS
神秘构造题。[题解](https://atcoder.jp/contests/arc206/editorial/13955)
比较合理的做法是爆搜出小规模的情况，人肉构造还是太吃注意力了。
### 典：P12444 [COTS 2025] 发好奖 / Hijerarhija
DFS 序的树形 DP。
挺有收益的一道题。虽然之前做过类似的题，但并不熟悉。
**小结**：
1. 这类题通常有两个转移方向：子树内、子树外。
2. 转移只需要**最简转移**，当前点不选的方案也可以更新到子树内，但我们不用管。就好像 LIS 也可以一次拼接两个数，但没必要。
3. 转移方向跟当前点的选择有关。我们当然可以搞个 $0/1/2$ 位来辅助。但更巧妙的是把状态描述改为左闭右开区间：$f_{i,j}$ 表示考虑 DFS 序中 $[1, i)$ 人，使用 $j$ 奖金的最大积极性。
树上背包的经典优化技巧能不能用于这道题？
### P12449 [COTS 2025] 吸尘 / Usisavač
又被构思题创飞了。
我们定义高度 $h_i$ 为 $i$ 往子树中能走的最远距离，$d_i$ 为深度。
经过一定的手玩，我们发现在高度大的位置，每条边至少经过 $4$ 次。并且下界可达。
而高度小的边（其较深端点 $i$ 满足 $h_i < r$）至少 $2$ 次。并且下界可达。
又由于 DFS 的原因，又一条从 $1$ 到叶子的经过次数还能再 $-1$。我们让这个叶节点为最深的点即可取到最优解。
$$
ANS = 4(n-1) - 2\sum_i [h_i<r] - \max_i d_i
$$
其中 $2\sum_i [h_i<r]$ 是仅和 $r$ 有关的，可以用双指针轻松求解，用个数组存下来（离线）。
### P12359 [eJOI 2024] 古迹漫步 / Old Orhei
虽然很简单，但是线段树优化游走还是有点意思的。
因为 `e` 数组 `M` 写成 `N`，调了半天。越界也是可能 WA 的，如果发现有玄学错误，记得检查边界。
### 难：P12448 [COTS 2025] 观草 / Trava
套路数据结构题。
我还是喜欢从代数角度推理。
**做法一**：
常见技巧：
$$
\sum_i{a_i} = \sum_{t \ge 1}{t\sum_i{[a_i=t]}} = \sum_{t \ge 1}{\sum_i{[a_i \ge t]}}
$$
对于本题，
$$
\sum_{1 \le i \le N-k+1}{\max_{i \le j \le i+k-1}{a_j}} = \sum_t{\sum_{1 \le i \le N-k+1}{[\max_{i \le j \le i+k-1}{a_j} \ge t]}}
$$
但是这个 $\max \ge t$ 并不好处理，我们不妨转换成 $\min \ge t$。拿最大值减去 $a_i$ 即可。
这样我们的目标就是对每个 $t$，求满足 $[a_i \ge t] = 1$ 的长为 $k$ 的区间数量。
我们可以维护 $cnt^t_k$ 为长为 $k$ 的极长区间数量，$sum^t_k$ 为长度和。但我们不可能每次都扫一遍 $t$，所以我们维护的 $cnt$ 和 $sum$ 为各个 $cnt^t_k$ 和 $sum^t_k$ 的和。
$$
Query(k) = \sum_{i\ge k}{(sum_i + (-k+1)cnt_i)}
$$
而且 $t$ 的范围很大，我们可以将 $a$ 排序后，每次加入一个 $a_i$ 的时候，把历史中的 $t$ 都结算一下（就是几何的**扫描线**）。这里也可以用**左闭右开**技巧，每次只结算历史的，而不结算当前的，这样好写。
还需要一个并查集来维护。
此时我们解决的**静态问题**。
关于修改，注意我们修改的 $a$ 的定义，所以变成 $-1$，也就是在我们对 $t$ 扫描时出现得晚了一个单位。这个对 $cnt$ 和 $sum$ 的影响是在可控范围内的，写一个二分和区间修改即可。
**做法二**：
类似 NOIP2024 T4，计算每个点的贡献，最后好像可以用 CDQ 处理修改，但我不会（
### CF2151E Limited Edition Shop
我们不妨重标号使得 $b = [1,2,\dots,n]$。记 $S$ 为 Alice 选择的物品集合。
**OBS**：$S$ 合法 $\Leftrightarrow \forall i < j, a_i > a_j$ 若 $a_j \in S$，则 $a_i \in S$。
换言之，若 $a_i \notin S$，则 $a_j \notin S$。
于是 $f_{i,j} = $ 考虑 $a$ 的前 $i$ 个元素，最大 $\notin S$ 的元素为 $j$ 的最大价值和。
**转移**：考虑 $f_{i-1,j}$ 向后转移。若 $i$ 被选择，转移到 $f_{i,j}$，需要满足 $j < a_i$；若不选择，转移到 $f_{i,max(j,a_i)}$，不需要条件。
$\max$ 可以分讨展开，接下来用线段树维护 DP 数组即可。
**小结**：
我们设计状态的时候，把限制较为直接的搬进状态里是更有利于转移的。
原本的想法：$f_{i,j}$ 表示前 $i$ 个元素，只考虑 $\le j$ 的元素的最大价值和。
它无法进行优化，甚至 $O(n^2)$ 都要上数据结构优化。
### 难：P11239 [KTSC 2024 R2] 跳跃游戏
暴力 DP：$f_i = $ 跳到 $i$ 的最大得分。$f_i = \max(f_{i-1},f_{i-K} + A_{i-K})$。
为了方便，把 $A$ 整体右移一下。$f_i = \max(f_{i-1},f_{i-K} + A_i)$。
**Trick 1**：注意到我们只关心，后 $K$ 位的值，所以可用循环数组。更新时，$f_{i \bmod K} \leftarrow \max(f_{i \bmod K} + A_i, f_{(i-1) \bmod K})$。等价于 $+ A_i$ 后与前一个数 chkmax。
这个 trick 是经典的。
**OBS 1**：$A$ 的相同值极长段的数量是 $O(Q)$ 的。
我们考虑把若干个连续的、相同的 $A$ 合在一起转移。
```
L-----
---x-----
---y-----
---z-R
```
该图是一个 $A$ 段在 $f$ 上的投影形态。`L` 和 `R` 是端点，`x`、`y`、`z` 都是是与 `L` 对齐的位置。
我们批量处理第一行：
**OBS 2**：对每一位 $+A_i$ 再与前一位 chkmax 等价于，集体 $+A_i$ 后再集体 chkmax。
于是我们可以用线段树维护（先假设 $K$ 比较小）。由于 $f$ 是单增的，所以循环之后就是两段单增拼到一起，chkmax 可以通过二分 + 区间覆盖实现。
**贪心**：从 `x` 开始，不需要考虑 $f_{i-1}$ 的转移情况，因为总是不如 $f_{i-K}$ 优。
于是从 `x` 到 `z` 都可以批量加，最后再补加 `z` 到 `R`。
**离散化**：离散化是数据结构优化**后**考虑的，此时的 $K$ 比较大，但由于 $A$ 的段数有限，所以投影到 $f$ 上的关键点也有限。
### 弱项：P11915 [PA 2025] 瞬间传送 / Teleport
枚举答案是最优化问题的常见技巧，其优化就是二分答案。
从大到小枚举能获得更多信息。
我们设当前枚举到的答案为 $ans$。我们需要检查是否存在 $0$ 边 $(u,v)$ 使得任意 $(i,j)$ 的距离 $\le ans$。
我们考虑用 $(i,j)$ 淘汰 $(u,v)$。
若 $d(i,j) > ans$，设 $d(i,u) \le d(i,v)$，则需要满足 $d(i,u)+d(v,j) \le ans$，否则 $(u,v)$ 就是不可行的。可以证明，我们不需要考虑 $d(i,v)+d(u,j)$ 的情况，因为这种方案不如不用 $(u,v)$。
我们可以枚举 $i$，对每一个 $v$，维护 $\max_{d(i,j)>ans}d(v,j)$（看题解的时候没理解到这里也是跟 $i$ 有关的）。
这里的实现需要一些均摊。
**小结**：
都是一些很朴素的程序设计技巧，但显然我并不熟练。
### CF786B Legacy
线段树优化建图模板。