题目列表

基于重链剖分（树链剖分）将树上路径映射为连续区间，并使用线段树维护单点修改与路径权值和、最大值查询。

将三颗棋子的跳动建模为二叉树结构，利用最近公共祖先（LCA）思想求两状态间最少跳动次数，用批量倍增加速收缩求根。

通过预处理节点到根的距离与倍增最近公共祖先 (LCA)，以 O((n + m) log n) 计算树上任意两点间的最短距离。

Kruskal 算法构建最小生成树，通过树上倍增 LCA 同时维护路径最大边权与严格次大边权，枚举非树边替换求严格次小生成树。

一次迭代 DFS 标出进入/离开时刻，把每个子树压成连续区间，祖孙判定化为 O(1) 的区间包含比较，总复杂度 O(n+m)。

区间乘与区间加统一为仿射变换 x→bx+c，线段树用（乘，加）双分量懒标记复合下推，O((n+m)log n) 维护区间和模 P。

通过 BFS 预处理树上倍增表快速求解最近公共祖先（LCA），利用深度公式 dist(u, v) = depth[u] + depth[v] - 2 * depth[lca] 在 O(log n) 时间内回答两点间距离。

使用两个树状数组分别维护差分序列及其加权和，将区间加与区间查询均优化至对数复杂度。

线段树维护区间和与最大/最小值，单个值开方至多变化 5 次即收敛到 0/1，用整段剪枝把区间开方均摊到 O((n+m)log n)。

利用双指针预处理每个位置最远无重复左端点，通过二分分段结合 ST 表在 O((N+M)log N) 时间内查询区间内最长无重复子区间长度。

用倍增递推建 ST 表预处理所有 2 的幂长度区间的最大值，每次询问取两块可重叠的 2 的幂区间求 max，O(1) 回答区间最大值。

预处理所有 2 的幂长度区间的最大值建成 ST 表，每次询问用两个可重叠的 2 的幂块 O(1) 求出区间最大值。

使用二维树状数组配合容斥原理维护二维矩阵的单点加与子矩阵和查询。

把导线看成边、焊点看成点，按连通块统计奇度端点与度数大于 2 的焊点；每块代价为 high + o/2，o=0 时特判为 max(2, high+1)。

将特征数对建模为有向图中的边，转化为用最少有向路径覆盖所有边，利用并查集分连通块结合度数差统计欧拉路径段数。

用度数全偶判定欧拉回路存在性，再用 Hierholzer 贪心延伸闭合路径并逐路口拼接，构造经过每条街恰好一次并回到起点的回路。

把长度 K 的 01 子串视为 de Bruijn 图的边，用 0 优先的 Hierholzer 求欧拉回路得到 M=2^K 的环，再旋转到唯一的全 0 串处，得到字典序最小方案。

答案 = 原连通块数 - 1 + 删点最大裂块数：一次迭代 Tarjan 维护 dfn/low，非根点裂块数 = 1 + low ≥ dfn 的孩子数，根等于子树数，O(P+C) 求最大值。

删点后的失联点对数只由各连通块大小的平方和决定，用一次迭代 Tarjan 求出每个割点切出的子树大小即可 O(n+m) 统计。

通过度数与基图连通性判定无向/有向图欧拉回路存在性，利用当前弧优化 Hierholzer 显式栈在 O(n+m) 内构造回路边序列。

使用 Tarjan 算法线性求解无向图割边（桥）数量，用边的唯一编号正确处理重边，并通过迭代栈避免深度递归栈溢出。

求添加最少边使无向图边双连通：Tarjan 边双缩点得到树，统计叶子节点数 L，答案为 (L + 1) // 2。

灾区就是无向图的割点：一次 Tarjan DFS 维护 dfn/low，非根点存在孩子 low ≥ dfn、或根在 DFS 树里有两棵以上子树即为灾区，O(N+M) 统计。

Tarjan 缩点将有向图转化为 DAG，利用半连通等价于链的性质，在去重后的 DAG 上通过拓扑排序 DP 求最长链及其方案数。

Tarjan 算法强连通分量缩点为 DAG，任务 A 答案为入度为 0 的强连通分量数，任务 B 答案在仅 1 个强连通分量时为 0，否则为入度为 0 与出度为 0 分量数的较大值。

Kosaraju 两遍迭代 DFS 把互相可达的奸细缩成强连通分量，答案即缩点后 DAG 中入度为 0 的分量个数。

把收买与证据关系建成有向图，SCC 缩点成 DAG 后只需收买入度为 0 的分量并各取最低价，源点不可收买时输出不可控点的最小编号。

把「认为」关系建成有向图，SCC 缩点后被全员认可等价于唯一出度为 0 的汇点，答案即该分量大小。

将每个小朋友糖果数的相对约束转化为差分约束系统，通过栈优化 SPFA 求解最长路及正环检测。

把 24 小时需求写成前缀和的差分约束，二分总雇佣人数 M 并用 SPFA 最长路判定可行性。

将牛的相对顺序、好感距离上限与反感距离下限转化为差分约束系统，通过两阶段 SPFA 分别判断全局负环与求 1 到 N 的最短路。

通过全图 SPFA 判定负权回路，并在无负环时以指定源点求解单源最短路。

把选点问题改写为前缀计数的差分约束系统，三类不等式建图后用 SPFA 求最长路，逐分量最小可行解的终点值即最少选点数。

把道路连通块缩点后航线构成 DAG，按拓扑序逐块跑 Dijkstra，块间负权边在目标块处理前即已定值。

Karp 最小平均权圈：O(nm) 递推恰好 j 条边的最小权行走表 F[j][v]，再按 min-max 见证分数公式一次扫描得到 μ*，整数精确舍入到 8 位小数。

将字符串首尾两位字母缩点建图，转化为 0/1 分数规划与 DFS-SPFA 判正权环求解最大环串平均长度。

将费用作为状态维度拆点，运用 Dijkstra 算法求出每种费用下的最小时间，再单调扫描提取 Pareto 最优前沿。

把「位置 + 剩余油量」并入状态建 O(N²K) 个点，行驶/强制加油/增设三类非负权转移跑堆优化 Dijkstra，终点弹出即最小费用。

通过 6 次堆优化 Dijkstra 预处理起点与 5 个亲戚间的两两最短路，结合全排列枚举拜访顺序求得最少总耗时。

在有向图上通过正反向 SPFA/队列松弛预处理前缀最小买入价与后缀最大卖出价，枚举中间中转城市求解最大单笔贸易利润。

Kruskal 求出最小生成树后，用倍增预处理树上每段的（最大边权，严格次大边权），逐条非树边做一次最优换边，取严格大于 MST 的最小权值和。

二分答案最大边权，将大于阈值的边赋权为 1、其余赋权为 0，通过 0-1 BFS 判定不超过 K 条长边的最短路径可行性。

建立正向图与反向图，分别以聚会农场为源点运行两次堆优化 Dijkstra 算法，求出所有牛往返最短路之和的最大值。

每个结点同时保留最短与次短两个距离标签，堆优化 Dijkstra 用严格开区间登记候选，一次弹堆直接得到第二短路长度。

利用最小生成树各权值边数固定且缩点连通性等价的性质，结合同权边最多 10 条的约束，按权值段枚举合法边集组合并通过乘法原理计数。

通过 WQS 二分为白边附加额外权值，利用凸性将恰好 need 条白边的生成树转化为无约束的带权最小生成树。

正难则反，答案 = 26^M − 不含任何单词的串数；用 AC 自动机构造状态（补全转移表、沿 fail 链下传「已命中」标记），再按长度做滚动数组计数 DP，复杂度 O(26·Σ|w|·M)。

严格次小生成树换边法：Kruskal 求出 MST 后枚举非树边，用树上 BFS 求环上最大边权作替换候选，过滤等权换边取最小，即得严格第二小的运输方案。

利用 Dijkstra 求解单源最短路后，根据边权正权性将最短路径生成树转化为各节点前驱父节点的独立选择，应用乘法原理统计方案数。

所有文字段建 trie，母串每个起点从根同步逐层下走并标记到过的节点，每段答案就是自身路径上最深的「出现过」节点深度。

使用 AC 自动机构建 fail 树，通过 Trie 前缀计数与拓扑逆序自底向上聚合子树权值，在线性时间内统计多模式串出现次数。

固定子串左端点，用 Z 数组一次求出该段所有前缀匹配长度，把第二个 A 的起点转成连续右端点区间，按偏移递增扫区间并去重，O(n²) 计数 A+B+A 子串。

用 AC 自动机求最长可匹配后缀，配合字符栈与状态栈保存历史；命中屏蔽词即弹栈并回退自动机状态，把「每次删除后重头扫描」化为对 S 的一趟线性扫描，复杂度 O(26·Σ|t_i| + |S|)。

把单词反转后建字典树，后缀关系变成祖先关系；按子树大小升序 DFS 得到最优填写顺序，答案即各节点与父节点的序号差之和。

构建字典树配合动态规划判定文章前缀可达性，利用单词长度极小的特点常数级转移与剪枝。

w 是某周期无限串的子串时，合法长度恰为 w 的周期：用 KMP 失配函数求最长 border，答案即 L − fail[L]，一次线性扫描完成。

利用 KMP 的 border 性质与失配指针链，将求最大周期转化为求每个前缀的最短正 border，通过路径压缩在 O(n) 时间内完成前缀周期求和。

用正反双向滚动哈希把每个块及其反转编码成同一个 O(1) 整数指纹，逐 k 去重计数取最优。

把 s 接成 s+s 后从下标 1 找 s 的首次再现，该位置就是整除 n 的最小周期 d，答案 n//d；CPython 的 find 用 Two-Way 算法线性完成，与 KMP 同阶。

求串的全部 border 长度：KMP 前缀函数只给最长 border，沿 pi 链反复回溯即可枚举全部，线性时间。