题目列表

先做子树内精确距离 DP，再做一次换根，把父亲方向的精确距离贡献传给儿子，最终累加 0..K 层即可。

设 dp[u] 为以 u 为根能得到的最大二叉树高度，把最深孩子放到兄弟链最后，就有转移 dp[u]=儿子数+max(dp[child])。

设 dp[u] 表示必须包含 u 的最优连通块和，自底向上只吸收正贡献子树，就能在线性时间求树上最大连通子图和。

在线段树中同时维护区间 1 的数量和最长连续 0，并用左优先递归把目标区间最靠前的若干个 0 填成 1。

用树链剖分把树上路径拆成若干个 DFS 序区间，再在线段树中同时维护区间和与区间最大值。

把安装与卸载操作转成根到点路径设为 1、子树设为 0，再用树链剖分配合线段树维护区间赋值和区间和。

按右端点升序贪心处理请求，只要整段畜栏最小剩余容量仍大于零就接下，并用线段树维护区间最小值。

把区间按长度排序后做双指针，在线段树上维护当前长度窗口内的最大覆盖次数，找到最小可行长度差。

把每个乘车请求看成区间装载，按终点升序且同终点按起点降序贪心接单，再用线段树维护路段最大占用。

把城市之间的每一段铁路看成一个位置，请求对应区间 `[O,D-1]` 的整体加法，能否接单只取决于这段区间的最大占用是否超过座位数。

一次染色只能填补两个已黑点之间的空隙，因此答案等价于：两端点初始为黑，且每段初始白色空隙都被至少一个活跃操作跨过。

不要把删除操作当成模除法，而要把每次乘法看成一个位置：插入时赋值为乘数，删除时改回 1，用线段树维护全局乘积。

在线段树节点同时维护区间和与区间最小值，区间加时用同一个懒标记同步更新这两个量。

把灯的开关状态看成 0/1 数组，区间翻转时用 `区间长度 - 当前开灯数` 更新节点，再用懒标记维护整段翻转。

把题意翻成区间约束后，核心只剩查询 `(Y,X)` 中间已知年份的最大降雨量，再配合年份是否完整连续做四类判定。

把每个元素看成最终都会被某个不小于它的相邻块吞并一次，它的最优贡献是左右第一个不小于它的值中的较小者，用单调递减栈即可线性求解。

把每个 K 对应的剩余作业看成一个后缀，预处理后缀和与后缀最小值，就能在线性时间内求出删去最小值后的最大平均分。

先把同一坐标上的星星亮度合并，再把题目转成一维数组上固定长度窗口的最大区间和，用前缀和线性扫描即可。

用线段树维护区间最大值；查询时返回区间最大，更新时在单点位置做 `max(原值, 新值)` 的只升不降修改。

按高度从低到高处理平板，并维护每个单位小格当前最高支撑高度；每块平板左右支柱的长度就是当前高度减去对应边缘小格的最高支撑。

用线段树维护区间里空地数与树苗数，把状态分成老树、空地、树苗三类，就能同时处理整段砍树、局部补种和树苗损失统计。

用 defaultdict 建立单词到文章编号列表的倒排索引，并在每篇文章内先去重。

把所有模式串插入字典树，并在每个前缀节点记录经过它的模式串数量；查询串走到终点后的计数就是答案。

把每个值左边更大元素的个数记为 $c[x]$，则做完 $k$ 轮冒泡后的逆序对数就是 $sum(max(c[x]-k,0))$，再用树状数组维护 $c[x]$ 的动态分布。

先找出本来就不必移动的最长严格递增后缀，再用树状数组统计每头前缀奶牛插入有序部分时应后移的步数。

先把所有彩珠按坐标打平成 `(位置, 颜色)` 序列并排序，再用双指针维护覆盖全部颜色的最短区间。

把地板看成容量为 k 的缓存，缺车且地板已满时始终淘汰未来最晚再次被请求的车，再配合下一次出现位置预处理即可得到最优答案。

前 k 轮已经能区分所有 x，当且仅当前缀询问的 lcm 等于 lcm(1..n)，因此答案就是所有必需质数最高幂第一次被覆盖轮次的最大值。

先把四个面的单位三角形按立体共边关系建成度数不超过 3 的图，再做带父边与值域边界的记忆化搜索，分别取当前节点左右子树的最优解。

把树定根后自底向上维护子树向上延伸的最大未截断衰减，若某个儿子子树再经过父边就会达到或超过初始强度，就必须在该儿子处安装放大器。

利用叶子枝长公式 limb(x)=min((d(x,i)+d(x,j)-d(i,j))/2)，递归删去一个叶子并累加其独有边长，最终得到整棵树的总重量。

把所有加密操作按相反顺序依次撤销，其中分别实现栅栏密码、维吉尼亚密码和 QWE 键盘码的逆变换即可还原原文。

把字符串复制成两倍长度后，用最小表示法比较两个候选循环位移并整段淘汰较差起点，在线性时间求出字典序最小表示的起点。

把每种颜色的首末出现位置看成区间，用栈扫描检查区间是否只存在包含关系；最大栈深就是最少轮数。

把平台序列建成最大笛卡尔树，递归计算每个子盆地先灌到根高度、再整体上涨的体积时间，从而求出各平台被淹没时刻。

把“灯亮”和“可达”分开维护，从起点做 BFS；每次开灯后，新亮房间若挨着访问区域就立刻变成可达。

把“初始朝上”和“初始朝右”两种可能同时打包成一个六维状态，用 BFS 求一套公共指令的最短长度。

用 9 位掩码维护每格候选数字，结合数独约束与大小关系反复传播，再按候选最少的格子搜索。

把每种特性的前缀出现次数都减去第一种特性，转成前缀差分状态；相同状态之间的最远距离就是答案。

二分最大位移后，把每个区间转成带最早可接点和最晚失效点的任务，按失效点最小优先贪心推进覆盖前缀。

枚举罪犯和星期几，在线性扫描证词时判断每个人是否必须恒真或恒假，再检查能否凑出恰好 N 个说谎者。

先在外层 DFS 枚举单顺、双顺、三顺的拆法，再对剩余牌型做记忆化搜索，精确求出最少出牌次数。

每次贪心选择当前能让最多乘客少 1 分钟的那段路，把它的行驶时间减 1；这次收益由提前效果能传播到的连续区间内下车人数决定。

按低位更重要的顺序给字母分配数字，每次赋值后立刻检查已经能确定的低位列是否满足进位加法，从而提前剪掉大量无效分支。

先按题目给定优先级把表达式递归下降解析成语法树，再用多组模数代值比较签名，快速判断哪些选项与题干恒等。

先判断愿望关系能否构成唯一的整环，再在正反两个环序中统计最优旋转能保留多少人不动，答案就是 n 减去这个最大值。

先在反图上从终点标记可达点，再筛出所有安全点，最后只在安全子图中做 BFS 最短路。

把树按深度分层后，按层搜索每轮在当前还会感染的点里切掉一个子树，最大化保住的人数。

把输入串看成 BWT 的最后一列，排序得到第一列，再用同字符同出现次序建立 LF 映射，从 p 逆推原串。

按冒号切成 8 组后分别去前导零，再找最前面的最长连续 0000 段，用一次 :: 替换即可。

把 a 看成带最早开始时间的单位作业，用大根堆贪心生成最优等待时间，再把大等待与小 b 配对得到最小总代价。

把合法区间改写成不存在 x_i>y_j 的冲突对，先用树状数组求每个位置的第一个冲突点，再用双指针维护最长合法区间。

按位置排序后，分别用两次单调队列维护左右 D 范围内的最大高度，再判断是否都达到当前高度的两倍。

把横纵坐标按 n 分成完整块和残块，利用模 n 余数的一一配对，常数时间统计整块与右下角残块贡献。

按固定元素是否出现过来统计不同元素个数之和，把每个长度的贡献化成两段等比数列求和。

把 x 分解成质因子后，每个指数里完整的 3 个一组都能提出到根号外，因此答案是各质因子 p 的 floor(e/3) 次幂之积。

证明每杯水在第一次烧开前最多只值得被预热到 50 度，于是总温度增量是 100 加上其余 n-1 杯各 50。

先判图中是否有孤立点；若没有，就对每个连通块的生成树二染色，直接构造两个互不重叠的覆盖方案。

在模板范围内搜索，并记录每个模格子第一次对应的绝对坐标；若同一模格子被不同绝对坐标到达，就能无限走远。

把机器人所在格点和朝向一起作为状态做 BFS，并预处理中心能否站在某个格点。