题目列表

先求从 1 号景点出发能到达的全部景点；在这些点上按边的较低端高度降序、边长升序做 Kruskal，可以在保证可达景点数最大的前提下，把总滑行距离压到最小。

二分最大允许造价 T。对每个 T，只看二级造价不超过 T 的边是否能连通全图，再看一级造价不超过 T 的边最多能提供多少条一级公路，从而判断可行性。

每周只新增一条边，因此当前最小生成树只可能通过“接上一条新边”或“用新边替换环上的更大边”发生变化；维护最小生成森林即可在线输出答案。

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

题面按轮修路的过程本质是在构造欧几里得最小生成树，最终总长度就等于 MST 边长之和；点数较大时直接用 Prim 求解即可。

这是带门槛的最小生成树：只有距离平方不小于 c 的边允许使用，直接在完全图上做 Prim，若中途出现不可达点则答案不存在。

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

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

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

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

在保留成树的前提下，一条边必走两次，而点 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] 表示一段石子合并成一堆的最小代价，枚举最后一次合并的断点并用前缀和计算区间总和。