题目列表

先做子树内精确距离 DP，再做一次换根，把父亲方向的精确距离贡献传给儿子，最终累加 0..K 层即可。

按右端点升序贪心处理请求，只要整段畜栏最小剩余容量仍大于零就接下，并用线段树维护区间最小值。

把区间按长度排序后做双指针，在线段树上维护当前长度窗口内的最大覆盖次数，找到最小可行长度差。

把每个乘车请求看成区间装载，按终点升序且同终点按起点降序贪心接单，再用线段树维护路段最大占用。

把题意翻成区间约束后，核心只剩查询 `(Y,X)` 中间已知年份的最大降雨量，再配合年份是否完整连续做四类判定。

把每个元素看成最终都会被某个不小于它的相邻块吞并一次，它的最优贡献是左右第一个不小于它的值中的较小者，用单调递减栈即可线性求解。

先把同一坐标上的星星亮度合并，再把题目转成一维数组上固定长度窗口的最大区间和，用前缀和线性扫描即可。

用线段树维护区间里空地数与树苗数，把状态分成老树、空地、树苗三类，就能同时处理整段砍树、局部补种和树苗损失统计。

用 defaultdict 建立单词到文章编号列表的倒排索引，并在每篇文章内先去重。

把每个值左边更大元素的个数记为 $c[x]$，则做完 $k$ 轮冒泡后的逆序对数就是 $sum(max(c[x]-k,0))$，再用树状数组维护 $c[x]$ 的动态分布。

先找出本来就不必移动的最长严格递增后缀，再用树状数组统计每头前缀奶牛插入有序部分时应后移的步数。

先把所有彩珠按坐标打平成 `(位置, 颜色)` 序列并排序，再用双指针维护覆盖全部颜色的最短区间。

把所有加密操作按相反顺序依次撤销，其中分别实现栅栏密码、维吉尼亚密码和 QWE 键盘码的逆变换即可还原原文。

把平台序列建成最大笛卡尔树，递归计算每个子盆地先灌到根高度、再整体上涨的体积时间，从而求出各平台被淹没时刻。

把每种特性的前缀出现次数都减去第一种特性，转成前缀差分状态；相同状态之间的最远距离就是答案。

先在反图上从终点标记可达点，再筛出所有安全点，最后只在安全子图中做 BFS 最短路。

把合法区间改写成不存在 x_i>y_j 的冲突对，先用树状数组求每个位置的第一个冲突点，再用双指针维护最长合法区间。

按位置排序后，分别用两次单调队列维护左右 D 范围内的最大高度，再判断是否都达到当前高度的两倍。

先算原始积水，再把每个位置改低后真正受影响的左右连续区间拆开重算，从而在线性时间求最优修改。

把单个站点总代价看成绝对值和函数，先取中位数区间平台，再从左右两条单调代价序列中归并取前 k 小。

把位置、当前颜色和是否刚施法作为状态，在四维状态图上做 Dijkstra 求最小花费。

检验值 y(W) 随阈值 W 单调不增，用前缀和在 O(n+m) 内计算一次 y(W)，再二分找到最接近标准值 s 的位置。

把前 k 份订单是否可满足做成差分检查函数，再二分第一份出问题的订单编号。

把 G 记成 +1、R 记成 -1，问题就转成最长和为 0 的子数组；记录每个前缀和第一次出现的位置即可。

预处理每对单词的最小合法重叠长度，再用 DFS 在每词最多使用两次的限制下搜索最长接龙。

先统计每个 t 的倍数里有多少齿轮，再用 C(cnt[t],k) 算 gcd 是 t 的倍数的方案数，最后按倍数从大到小容斥还原精确 gcd。

先算总状态数 m^n，再减去所有相邻房间宗教都不同的安全状态数 m·(m-1)^(n-1)。

把每轮操作看成当前酒量加上 b 再对 a 取模，最小正体积就是 gcd(a,b)，再用 exgcd 求 b·y-a·x=g 的最小正解。

先用 exgcd 求 ax+by=-c 的一组特解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，把矩形范围限制都转成对 k 的区间约束，最后求区间交集大小。

先用 exgcd 判断 ax+by=c 是否有整数解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，通过不等式求出正整数解对应的 k 范围。

把两只青蛙第 t 次跳跃后位置相等写成 (m-n)t≡y-x(mod L)，再用扩展欧几里得求最小非负解；若 gcd(m-n,L) 不能整除 y-x，则无解。

把状态定义成“当前所在牧场 + 已改造道路数”。走一条边时要么正常付边权，要么消耗一次改造机会把这条边代价降成 0，在状态图上跑 Dijkstra。

把状态定义成"当前所在城市 + 已用卡数"。走一条边时要么正常通过，要么额外消耗一张卡把这条边代价减半，在这个状态图上跑 Dijkstra。

按牧场过路费从小到大加入 Floyd 中转点，维护边权和最短路；每次加入新中转点后，用“边权和 + 当前允许最大点权”更新所有点对答案。

先求出一条 1 到 N 的最短路。只有这条路上的边被封闭才可能让答案变大，因此依次禁用这些边并重跑最短路取最大值。

把已有电线当成 0 权边，把距离不超过 M 的点对当成可补的新边，在这张图上跑最短路求从 1 到 N 的最小补线长度。

先 Floyd 求每个连通块内任意两点最短路，再枚举跨块连边，用两端点到各自块内最远点的距离更新合并后的最小直径。

先求出一条从 1 到 N 的最短路。只有这条路上的边加倍后才可能让答案变大，因此枚举这条路上的每条边临时加倍，再重跑 Dijkstra 取最短路增量最大值。

只需要比较两种送货顺序：PB->PA1->PA2 和 PB->PA2->PA1。图是无向图，因此求出 PB 到两点的距离和 PA1 到 PA2 的距离后即可直接取最小值。

所有奶牛都要判断能否在 M 秒内到达同一个目标点 1，所以只需从 1 号草地做一次 Dijkstra，再按奶牛编号检查距离是否不超过 M。

这题不是最短路求和，而是最小化路径上的最大边权；点数只有 300，可以直接用 Floyd 的 min-max 转移求所有点对的最小瓶颈路。

往返距离等于 i 到 x 再加 x 到 i；原图从 x 跑一次 Dijkstra，反图再从 x 跑一次 Dijkstra，就能得到所有点的来回最短路。

利用无向图距离对称性，从每个喜欢的牧场各跑一次 Dijkstra，把到所有点的距离累加后取总和最小的牧场。

路径加可以先做树上差分，再把子树和展开成 diff 的加权求和；结合 LCA、DFS 序和两棵树状数组，就能在线维护路径加与子树和查询。

两点间最优通信稳定性等于所有路径中最小边权的最大值，这正是最大生成森林上的路径最小边权；先 Kruskal 建最大生成森林，再用倍增 LCA 查询路径最小边。

对每个节点预处理根到它路径上的 depth^k 前缀和，再用 LCA 把路径拆成两段：sum(x)+sum(y)-2sum(lca)+depth(lca)^k。

把每台电脑的度数看成点权，询问就是树上两点路径点权和；预处理根到每个点的前缀和，再用 LCA 把路径拆成两段即可。

把每个兴奋值看成一个状态值，若某个兴奋值 x 能选择一个结束兴奋值为 y 的游戏，就连边 x->y；某个游戏能玩两次，当且仅当它的 e_i 能回到某个整除 w_i 的同 SCC 状态。

关键线路一定是桥；先用 Tarjan 找桥，再统计桥两侧是否都同时含有 A、B 两种服务，只要某一侧缺少其中一种服务，这条桥就是答案。

先把同高且连通的格子缩成强连通块，块间只能从高处指向低处，缩点后是一张 DAG，最少缆车数就是入度为 0 的块数与出度为 0 的块数的较大值。

Tarjan 回溯时若树边 u-v 满足 low[v] >= dfn[u]，说明 v 子树必须经过 u 才能连到外部，此时把点栈弹到 v 再加上 u，就得到一个点双连通分量。

先用 Tarjan 找出无向图中的所有桥，再把这些桥删掉，剩下的每个连通块就是一个边双连通分量。

先用 BFS 求出任意两座城市之间的最短骑士步数，再把“从已占领城市攻占一座新城市”的代价视作边权，整道题就转化成一棵最小生成树。

要求把 N 个点连成恰好 K 个连通块且总代价最小，本质就是最小生成森林；按边权从小到大做 Kruskal，连到只剩 K 个连通块时停止。

要求先用最少的边把全图连通，因此一定选 n-1 条边；再把这些边中的最大权值压到最小，直接按边权从小到大做 Kruskal，最后一条加入的边权就是答案。

把两棵树之间能否跳过去看成边，所有树都能互达所需的最小跳距，等于一棵最小生成树中的最大边长；用 Prim 求出这个临界值后统计能达到的猴子数量。

在保留成树的前提下，一条边必走两次，而点 i 的谈话时间会按它在树中的度数计入；把每条边改写成 2*l+c_u+c_v，再额外加上最小的起点费用即可。

因为边权是严格递增的 2^i，最优环一定在按边编号从小到大加边时第一次形成；先用并查集找到这条边，再在此前形成的森林里找两端唯一简单路径。

把每次有效连边变成并查集合并树上的一个新父节点，测试操作只给当前连通块根打标记，最后 DFS 一次把信息总量下传到所有原节点。

把每一列看成一个并查集集合，维护每艘战舰到队头的距离；合并时整体挂到另一列后面，就能在线回答两舰之间隔了多少艘船。