题目列表

对十个数字求变换传递闭包，再把每一位的可达数字数相乘。

在有向图上同时传播路径最低买价和最大已获利润。

按时间增量加入 Floyd 中间点，在线回答当前已重建村庄间最短路。

BFS 分层并在最短层边上累加方案数，支持重边。

二分允许的最高城市收费，用受限 Dijkstra 检查血量能否到达终点。

对配方超边做 Dijkstra 式松弛，再按最小成本递增顺序统计最优方案数。

把三类作物数量关系统一成差分约束边，并检测负环。

Floyd 同时维护最短距离和路径数，再按经过节点的路径比例计算重要度。

用位集传递闭包统计每头牛已知强于和弱于的数量。

Dijkstra 同时维护每点严格不同的最短与次短距离。

Floyd 预处理岛屿两两最短危险值，再累加指定访问序列相邻项。

把下界约束建成 0/1 边，SCC 判严格环后在缩点 DAG 上求最长路。

从节点 1 运行 SPFA，以最短路边数达到 n 判断可达负环。

以最小步长为模建立余数图，Dijkstra 求每类余数最早可达楼层。

把免费次数作为分层状态，在 n(k+1) 个状态上运行 Dijkstra。

用 heapq 实现带过期状态判断的 Dijkstra，求非负权有向图单源最短路。

把 x_c-x_c'<=y 转成 c' 到 c 的边，用最短路构造可行解。

Floyd 后枚举传送门端点，逐点对比较原路和两个传送方向。

先求树的直径，在直径上用双指针枚举长度不超过 s 的核区间，偏心距由两端距离与分支最大深度决定。

对每个中间点聚合邻居权值，用 S²−Σw² 得到距离为 2 的有序点对总和，用前两大权值求最大值。

把观察条件改写为深度等式，按 LCA 拆两段路径，用桶与树上差分在 DFS 中统计每个观察员看到的人数。

任选根 DFS 求每棵子树大小，边费用 = 边权 × |2·子树大小 − n|，一次遍历累加总费用。

二分答案，倍增 LCA 求路径长度，树上差分找所有超标路径的公共边并比较最大公共边权。

用树链剖分把子树与根路径映射成数组区间，双树状数组维护区间加与区间和，根路径和 O(log^2 n)。

树链剖分把路径拆成区间，按宗教拆成多棵动态开点线段树，只统计同宗教城市的评级和与最大值。

两条树上路径相交当且仅当某条路径的 LCA 落在另一条路径上，用距离等式 dist(u,x)+dist(x,v)=dist(u,v) 判断点在路径上。

重链剖分把祖先路径拆成 O(log n) 段连续区间，线段树维护段内最大已标记 dfn，逐链向上查询最近标记祖先。

用树链剖分把根到节点的路径拆成重链段，线段树维护段内黑点最小 dfn，从根侧逐段查询得第一个黑点。

最坏时间 = min(到两朋友距离) + 两朋友距离；A、B 取直径端点，三次 BFS 后 O(n) 扫描答案。

拓扑剥叶给每个节点分层，选层号最大的 k 个连通节点作核心，答案即第 k+1 大的层号。

根路径 G 前缀和配合倍增 LCA 容斥，O(log n) 回答路径上是否出现指定品种。

Luogu 无法提交 Codeforces 原题，解析已迁移至 codeforces/19D，本页仅保留入口。

用线段树双懒标记维护区间赋值与区间加，赋值覆盖加法、下传先赋值后加，查询区间最大值 O(log n)。

距离和最小的点即树的重心：用重心模板求重心再算距离和；另一解法用换根 DP 递推全部点的距离和。

等差数列区间加可拆系数用双 Fenwick 维护差分，也可用线段树等差数列懒标记，两者均 O(log n)。

线段树节点同时维护区间和与平方和，用懒标记支持区间加，方差由二阶矩公式 O(log n) 求出。

位掩码压缩集合 + 集合并运算，popcount 输出颜色种类数。

离散化后固定中间点，用两次树状数组扫描分别统计左小与右大个数，相乘求和得三元组总数。

用线段树双懒标记（赋值覆盖翻转）维护 01 序列，节点存 0/1 两套前缀后缀与最长连续段，单次操作 O(log n)。

树上边差分：P 对 u、v、lca 三个点做差分配置，Q 用 DFS 序子树和回答单边覆盖次数。

用倍增 LCA 定位每条路径的公共祖先，再以树上点差分四个端点标记统一汇总，求出被经过次数最多的点。

区间加与区间和模板题，可用懒标记线段树或两个 Fenwick 树维护。

把区间乘和区间加统一成仿射懒标记，维护模意义下的区间和。

用倍增表 up[u][j] 记录 2^j 级祖先，查询时先提深再同步跳，单次询问 O(log n)。

用重链剖分把树上路径与子树映射为 DFS 序连续区间，再由懒标记线段树维护区间加与区间和。

用翻转懒标记维护区间亮灯数量，整段翻转时数量取反、标记异或，单次操作 O(log n)。

树剖拆路径为 O(log n) 段，线段树四元信息维护正反序最大买卖差并支持路径加。

用线段树维护区间和与最大值，整段最大值不超过 1 时剪枝跳过开方，摊还 O(log n) 级单次操作。

线段树维护区间和、最大前缀、最大后缀和最大子段和，支持单点修改。

每个串压成 0/1 两个位掩码，线段树按位或合并区间约束，统计兼容二进制串数量。

找同色节点的直径端点并判共线，共线时按切断端点两侧第一条边后的连通块大小相乘计数。

对每条边断开后，利用最大子树方向唯一的性质沿 heavy 链倍增定位两侧重心，配合换根在 O(log n) 内枚举每条边。

从 1 号点 BFS，边权全为 1 时层数即距离，距离为 d 的点停止扩展并计数，一次遍历 O(n)。

线段树节点维护区间两端值与最长交替前后缀，合并时按跨中点边界是否交替拼接，单点翻转 O(log n)。

最大堆和最小堆维护前缀的较小一半与较大一半，奇数长度输出最大堆顶。

两个堆维护已输出排名左侧与右侧元素，使每次 GET 的目标值位于右堆顶。

有修改的堆 1. 自己维护堆+桶 2. 堆的过时元素删除

把每个递增二次函数看成有序序列，用堆做 n 路归并取前 m 项。

Fenwick 维护当前不相交线段的起点，并按秩寻找可能相交的前驱和后继。

补零后执行 K 叉 Huffman 合并，堆中同时维护权重与子树高度。