题目列表

通过中序遍历区间与二叉树子树一一对应的性质，建立 O(n^3) 的区间 DP 模型求最大加分，并通过记录各区间最优根节点递归输出前序遍历。

先求以 1 为根时的子树牛数与总代价，再通过换根公式 dist[v]=dist[u]+(total-2*sub[v])*w 线性求出最优集会点。

将用户数作为背包容量维度，利用树形背包 DP 求解在净收益非负条件下的最大转播用户数。

值域很小而位置很大, 于是把区间 DP 的维度反转: dp[i][v] 存从 i 合成 v 的最短结束位置, 答案取最大的可达 v.

用全局时间队列清理过期优惠票，再按票价分桶寻找最早可用且票价足够的地铁券。

把「恰好 k 个点又要连通」翻译成每个点的第二长臂长：答案是第 k+1 大臂长加 1，用直径中点求向下高度或剥叶分层都能直接算出。

把一次涂色看成一段连续区间，用区间 DP 让左右端点相同的字符共用一笔涂色，转移枚举拆分点，时间 $O(n^3)$。

两次 DFS：先根化建父子关系，再后序求每棵子树大小，边费用 = 边权 × |2·子树大小 − n|。

把插入过程反过来看：已入队的人在理想队形中是连续区间 [l,r]，设 dp[l][r][0/1] 记录最后插入者在左端还是右端，按区间长度递增向两侧扩张计数。

把环按断边展开成链，用同时记录区间最大与最小值的双状态区间 DP 处理负数的乘法，最后枚举所有断边取最优并按编号升序输出。

从指数级枚举合并顺序的暴力出发，利用相邻合并对应连续区间的性质，设区间 dp[l][r] 枚举最后一次合并的断点，用前缀和加速得到 O(n³) 区间 DP。

把函数调用关系看成 DAG，逆拓扑序求每个函数的整体乘法倍数，再正拓扑序从后往前传播加法的最终系数。

将动态删点与可达性等价转换为中间点编号受限的双向最大瓶颈路径，利用倒序 Floyd 动态规划在 O(n^3 + m) 内求解所有子图答案。

树上最大权独立集模板题：通过树形 DP 记录当前节点选或不选两种状态，自底向上合并子树最优解。

对角线前缀和 O(1) 查段收益，交换 max 后每条对角线单调队列滑动窗口，O(nm) 决策优化 DP。

通过 Tarjan 缩点将软件循环依赖转化为不可分割的超点，再连虚拟根构成树形结构，进行树上有依赖的背包 DP 求解。

通过树形 DP 求解树的最小顶点覆盖，根据结点放与不放两种状态在子树间转移。

通过 Tarjan 缩点将强连通分量内的边转化为完全采摘的点权，跨分量的边化为单次通行的有向边，再在 DAG 上利用拓扑排序求最长路。

通过倍增预处理图上任意两点间是否存在长度为 2^k 的路径，转化为边权为 1 的最短路问题并用 Floyd 求解。

把展开过程倒过来看：区间能折成一个字母当且仅当存在规则 c→xy 与分裂点把区间切两半；按区间长度递推的区间 DP，复杂度 O(L^3)。

先断环成链并复制数组，再设 dp[l][r] 表示一段珠子聚合后的最大能量，枚举最后一次合并的断点。

在有向无环图上逆向定义到达终点的剩余期望长度，利用全期望公式与拓扑序通过记忆化搜索在 O(n+m) 内求解。

把环复制成 2n 长数组，先教会链上的区间 DP（枚举最后一次合并的断点），再枚举所有长度为 n 的起点，同时维护最小与最大合并代价。

把已关灯集合压成包含起点的连续区间 [l,r]，用 f[l][r][0/1] 记录停在区间左/右端的最小耗电，区间 DP 一步扩展到相邻端点，O(n^2) 求解。

两种解法并列：线段树优化建图 + Tarjan 缩点把区间连边压到 O(log n)，在 DAG 上传播可达区间端点；以及不建图的 O(n) 双向扫描，靠「引爆集合是连续区间」和「右向射程在向左闭包时仍有效」直接求端点。

行只能单调向下，所以逐行决策；再证明走完一行后最优解必停在该行线段的端点，把每行状态压缩成左、右两个，得到 O(n) 线性 DP。

把「任意两点有两条边不相交路线」化归为「没有桥」，删桥缩成边双得到桥树，答案就是桥树叶子数的一半向上取整。

把每场游戏的两种可用赛车建模成 2-SAT 布尔变量，用「禁 A / 禁 B」两种情形覆盖 x 地图的三种取值，2^d 次 Tarjan 判定。

把删点后 S 是否分裂翻译成圆方树上的路径必经点，再用圆点前缀和与虚树环巡游 O(|S|log n) 回答每次询问

圆方树 + 赋权 + 树上路径贡献计数：方点权=BCC大小，圆点-1，树DP统计每点被(s,f)路径经过次数

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

把每个组看成一条连续链，按实力值递增处理；有多条链可接时接最短的，链比人多时冻结最长的，断档时整段冻结，答案取所有链长的最小值。

买下一个间谍就能免费得到他整条下游，于是真正要选的是「从哪些人进入」；互相可达的人缩成强连通分量只买最便宜的一个，缩点后 DAG 里只有入度为 0 的分量无人能揭发、必须直接收买。

正难则反：把「最小删边代价」翻成「最大保留边权和」，按边权降序并用并查集，两端块都含敌城时才必须删这条边。

Kruskal 求 MST 后枚举非树边换树边，倍增 LCA 同时维护路径最大与严格次大边权。

求 s 到 t 路径上最大边权的最小值（瓶颈路），可用 Kruskal、瓶颈 Dijkstra 或二分答案求解。

把直接买建成虚拟源点边，把优惠价建成礼物间边，转化为最小生成树。

多次询问无向图中点对的最大瓶颈路：Kruskal 建最大生成森林，倍增 LCA 上跳时维护路径最小边权，O(log n) 回答每个询问。

把打井建成虚拟水源点到田地的边、铺管建成田地之间的边，问题化为 n+1 点图上的最小生成树，Kruskal 求解。

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

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

两遍 Kruskal：第一遍先加水泥路求鹅卵石路下界 need 并标记被迫边，第二遍放回被迫边、补鹅卵石路到 k 条、水泥路填满，得恰好含 k 条免费路的生成树。

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

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

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

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

把三类作物数量关系统一成差分约束边，全点入队跑 SPFA 判负环，有负环即矛盾。

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

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

把 x_c-x_c'<=y 转成 c' 到 c 的边，初值取 0 全部入队跑 SPFA 做松弛；无负环即有可行解。

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

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

A[i] 全为正数，前缀和严格递增，于是「sum[k] ≤ T」具有二分性：在线解法从位置 0 从大到小试跳 2^i 定位最后一个可行位置，离线解法把询问按 T 排序后双指针右移推进。

矩形加、点查询：把矩形拆成 4 个带符号的二维差分点，用二维树状数组（外层 x、内层 y）求二维前缀和，单次 O(log²)。

用队列优化的 Bellman-Ford（SPFA）求非负权有向图单源最短路，只在距离被改小时重新入队。

以 map 精确分组差异核心、双 Trie DFS 激活和祖先链求和为主解，并对照 AC、二维扫描线与确定性线性做法。

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

利用扩展域并查集维护朋友域与敌人域，实现敌人的敌人是朋友的传递合并，统计不同团伙代表元数量。

带集合大小的并查集：M 合并时把小家族挂到大家族根下并把人数累加到新根，Q 输出 sz[find(a)]，均摊近似线性。

按编号前缀删点后最大连通块不超过 floor(n/2)：删 1..k 等价于只保留后缀，倒序加点用并查集维护集团大小，首个超过 n/2 的集团所在轮次即最小 k，复杂度 O((n+m)log n)。