题目列表

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

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

题目给的是完整邻接矩阵，直接用 Prim 维护每个未选点到当前生成树的最小连边代价，逐个把点加入生成树即可。

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

并查集合并已有道路并实时维护连通块数，最少新道路数就是连通块数减一。

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

把每个数出现后占掉这个位置，并查集维护“从某个值开始往后第一个没被占用的位置”，从而快速找到修改后的最小可行值。

用并查集维护若干元素所属的集合，操作 1 合并两个集合，操作 2 判断两个元素是否已经连通。

分别求出 A 公司里与 1 号同组的人数、B 公司里与 -1 号同组的人数，答案就是这两个连通块大小的较小值。

把关闭谷仓的过程倒过来看成重新开门，按倒序激活点并用并查集维护当前开着的连通块数量。

把每个格子看成一个点，出现连根关系就并查集合并两个编号，最后连通块数量就是合根植物的总株数。

先判定有向欧拉路存在条件，再把每个点的出边按升序走 Hierholzer，最后逆序得到字典序最小的欧拉路径。

把限制反向建图，用大根堆在反图上做拓扑排序，再把得到的序列倒过来输出，就能得到题目要求的最优顺序。

把函数调用关系看成 DAG，先反向求每个函数整体乘法效果，再正向统计每个加法函数最终会被乘上的系数。

在 DAG 上同时维护从起点到每个点的路径条数和所有路径长度总和，最后加上每次重新坐船返回的固定时间。

在 DAG 上按拓扑序传播精确分数流量，每个点把当前污水均分给所有出边，最后统计所有汇点的分数结果。

按拓扑序模拟神经元信号传播，只有 `C[i] > 0` 的点才向后继传值，非输入层先扣掉自己的阈值。

把记忆约束建成带权 DAG，在拓扑序上做最长路转移，`dp[i]` 表示第 i 次挤奶能安排的最早日期。

把先后约束建成 DAG，在拓扑序上做最长路 DP，`dp[i]` 表示完成第 i 头奶牛的最早结束时间。

把“某摄像头所在位置被别的摄像头监视”建成有向边，反复删除入度为 0 的点，最后剩下的摄像头数就是答案。

把每条推荐规则看成依赖一组前提题的规则节点，维护未满足前提数和前提最大完成天数，单调传播每道题的最早完成日。

利用每条边都从小编号指向大编号的天然拓扑序，按编号进行 DAG 最长路 DP。

分别用显式栈模拟前序、中序、后序遍历，其中后序用双栈避免深递归爆栈。

统计前序相邻且在后序中反向相邻的父子对个数，每出现一个这样的单孩子歧义点，答案就乘 2。

把每种宝物的件数做二进制拆分，转成若干件 0/1 物品后，再做一维 0/1 背包。

先按后缀表达式建树并求当前值，再从根向下传播“能否影响根”的标记，这样每个翻转询问都能 O(1) 回答。

后序计算每棵子树的正常表示和镜像表示，若二者相等则该子树对称，再用子树大小更新最大答案。

把“有相同萌元素”转成“有公共质因子”，每次修改后整树 DFS，沿根路径按质因子维护最近祖先栈即可回答所有查询。

先按优先级把中缀表达式建成语法树，再用显式栈按短路语义迭代求值，只统计真正访问到的子树里的短路次数。

用有序集合维护已插入节点，只看当前值的前驱和后继，取插入更晚者为父亲，再迭代输出后序遍历和最大深度。

利用后序末尾字符确定根，再在中序里切出左右子树区间，递归按根左右顺序输出先序遍历。

递归处理每个二分区间，先输出左右子树结果，再用区间内 0/1 的分布判定当前结点类型。

利用前序首字符确定根，再在中序里切出左右子树区间，递归按左右根顺序输出后序遍历。

把状态设成 (点, 当前时刻 mod k)，在状态图上跑 Dijkstra，转移时把时间补到不早于开放时刻且同余不变的最早值。

把问题转成从 1 到 a 是否存在长度恰好为 L 的游走，用奇偶分层图 BFS 求最短同奇偶步数。

把已访问顶点压成二进制集合，设 dp[mask][u] 表示走过 mask 且停在 u 时的最大路程。

每条边必须恰好有一个端点被选，因此图必须二分染色；每个连通块取两种颜色中较少的一侧。

先把每个点的邻接表按升序排序，再用逆序压栈实现非递归 DFS，用队列实现 BFS。

先用 Tarjan 建圆方树，再统计 x 到 y 在圆方树路径上经过了多少个原图割点。

固定路径中间的有向边，左右两端独立从两侧端点的其余邻居中选择，边贡献就是两个度数减一的乘积。

给释放名单两端补哨兵，设 dp[l][r] 表示释放两边界之间所有目标囚犯的最小代价，枚举第一个释放点。

把每一层看成连续区间，设 dp[l][r] 表示上一层支撑区间为 [l,r] 的方案数，再用区间包含和转到下一层。

设 dp[l][r][0/1] 表示已构成目标区间 [l,r] 且最后插入的人在左端或右端时的方案数，按大小关系向两侧扩张。

设 dp[l][r] 表示把目标子串 s[l..r] 涂出来的最少次数，若后面有与 s[l] 相同的字符，就尝试共用一次涂色。

设 dp[l][r] 表示区间 [l, r] 整体能合成出的最大值，枚举最后一次合并的断点，把两个相等子区间向上合并。

设 dp[i][v] 表示从位置 i 开始最短到哪里能合成值 v，利用两个相邻的 v-1 递推出更大的值。

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

设 dp[l][r] 表示删光当前区间 [l, r] 的最大收益，枚举这一步从左端或右端删掉多长的一段。

设 dp[l][r] 表示卖掉区间外所有零食后，剩余区间 [l, r] 能取得的最大收益，按当前天数转移左右端点。

设区间 dp[l][r] 表示一段石子合并成一堆的最小代价，枚举最后一次合并的断点并用前缀和计算区间总和。

按时间排序后，用高度状态记录最晚存活时间，逐个垃圾做吃或堆的转移。

把每个城堡的对手兵力排序并合并相同值，转成若干个阈值台阶，再做分组背包求最大得分。

把每个英雄的皮肤选择看成分组背包，按总花费做 DP，记录最多能得到多少种展示方式。

把相邻两天的价格差当作收益，按每天做一次完全背包，逐步更新手里的金币。

按 P_i 区分完全背包和多重背包，先二进制拆分再做一维最大值 DP。

用完全背包求每个面值的最少邮票数，再扫描最长连续可达前缀。

先按允许高度排序，再用多重 01 背包判断哪些电梯高度可达。

用偏移数组做 01 背包，记录智商和对应的最大情商，再在非负状态里取最大总和。

用前缀和优化的多重背包计数 DP，统计每种花最多取 a_i 盆时的摆放方案数。

把每座城堡能保留的高度看成前缀和，取所有城堡共同可达的最大高度。