颓废记录 - 2025

Re_FYCCCCTA · 2025-07-23 17:46:14 · 题解

7.2 P4001 [ICPC-Beijing 2006] 狼抓兔子

建立对偶图（样例对偶图如下图所示），狼只要封锁 0 到 13 的任意一条路径即可，所以在对偶图上跑最短路即可。

7.8 P2801 教主的魔法

考虑分块，对每个块内的元素进行排序。修改可看作对整块的修改与对块内前、后缀的修改，对整块的修改只需打标记，对块内前、后缀的修改暴力做然后排序。查询只需在每个块内二分即可。

7.10 P2014 [CTSC1997] 选课

有依赖的背包 dp，即树上背包板子题。设 f_{u,i,j} 表示只考虑以 u 为根的子树的前 i 个子节点，限重为 j 的最大价值。状态转移方程即为：

其中 v 为 u 的子节点，s_v 为 v 的儿子数量，与 01 背包不同的是，此处的 w 需要枚举。

与 01 背包一样可以滚动掉第二维，状态转移方程如下：

注意循环顺序。

7.11 P1896 [SCOI2005] 互不侵犯

状压 dp 模板题。设 f_{i,j,k} 表示考虑到第 i 行，第 i 行状态用二进制表示为 j（1 表示在此位置放了国王，0 表示没放），且共放置了 k 个国王的方案数。转移时从外到内枚举行数、上一行状态（设为 x）、当前行状态（设为 y）与防止国王数。当出现如下情况下任一时不合法：

1. 这两行总放置了超过 k 个国王，即 __builtin_popcount(x)+__builtin_popcount(y)>k。
2. 同行左右相邻，即 x&(x<<1)||y&(y<<1)。
3. 相邻行上下相邻，即 x&y。
4. 相邻行斜向相邻，即 x&(y<<1)||x&(y>>1)。

7.11 P2704 [NOI2001] 炮兵阵地

P1896 升级版。因为一个炮兵会影响到向上、向下两格的位置，所以设 f_{i,j,k} 表示考虑到第 i 行，且第 i 行状态为 j，第 i-1 行状态为 k 时的方案数。转移时需枚举第 i、i-1 与 i-2 行。最好将第一维滚动。

7.14 P2254 [NOI2005] 瑰丽华尔兹

7.30 P4819 [中山市选] 杀人游戏

把题目中的关系看成一个有向图。注意到对一个强连通分量里的任意一个非杀手的点查证就可以无风险地查证此分量中的所有人，因为对于每个分量里的点如果它临点没有杀手就可以继续遍历直到临点有杀手。所以我们先将原图缩点。

然后我们还可以注意到新图中从入度为 0 的点开始查证是最优的，因为对每个入度大于 0 的点查证不如查证有边连向它的点。根据此，我们可以得到一个初步的答案：1-\frac{k}{n}，其中 k 是入度为 0 的点的个数（因为要从 k 个强连通分量中每个都随机选一个（原图中的）点，每个点是杀手的概率是 \frac{1}{n}，总共就是 \frac{k}{n} 的概率失败）。

但我们忽略了一种情况：已经确定了 (n-1) 个人不是杀手，那么剩下的那个人一定是。出现这种情况当且仅当存在一个新图中的入度为 0，且其所有临点的入度均大于 1 的点。此时答案为 1-\frac{k-1}{n}（无论存在几个这样的点，都只减 1）。

7.30 P3302 [SDOI2013] 森林

与 P2633 Count on a tree 一样，在树上差分即可查询，连边操作就使用树上启发式合并，将点所在的树的大小小的连到大的，暴力更新小树的信息，树上启发式合并的时间复杂度是 O(\log n) 的。

注意更新小树的倍增父亲数组时上界要比 \log dep_u 大，主席树空间要开大点。

8.2 P2824 [HEOI2016/TJOI2016] 排序

考虑离线。二分答案，每次 check 就建立一颗线段树维护区间和，其中比二分的值大的就记为 1，否则就记为 0，然后处理每个操作，统计每个操作区间 1 的个数，然后直接两次区间覆盖完成排序，最后看 q 位置上的数字是不是 1，是的话说明这个值可以，否则不行。

8.3 P4219 [BJOI2014] 大融合

有两种做法：

1. 线段树分治：几乎与模板一样，唯一不同的是在询问时不把询问的边加上，即设一条边 (u,v) 在 s 时刻出现，在 t 时刻被询问，则此边的出现时间区间为：s \sim t-1 与 t+1 \sim m。

2. 线段树合并：对每个结点按 dfs 序建立权值线段树，每次加边就是合并两颗线段树，询问就查询根节点计算即可。

8.3 P3402 【模板】可持久化并查集

使用可持久化线段树维护并查集的 f 数组，但是不能路径压缩，只能按秩合并，所以还需要额外用可持久化线段树维护子树大小或深度。

8.4 P2617 Dynamic Rankings

带修的区间第 k 大。考虑树状数组套权值线段树，即每个主席树维护的信息由前缀改为树状数组内对应的部分，则每次求和、修改只需要修改 O(logn) 个权值线段树。

8.4 P3157 [CQOI2011] 动态逆序对

注意到：删除某个元素后的逆序对数 = 删除此元素前的逆序对数 - 此元素前面比其大的元素数 - 此元素后比其小的元素数。先处理出原序列子序列数，后两项使用主席树可以维护。但我们还需要支持单点修改（删除），所以使用树状数组套权值线段树解决。

（为什么降蓝啊，恼）（upd：回紫了欸）

8.5 P5490 【模板】扫描线 & 矩形面积并

对于矩形面积并问题，我们通常将其分成若干个不相交的矩形来处理，如图，其中每个颜色块都是一个矩形：

对于每个矩形，其面积 S=长\times 宽，宽很容易求得，就是相邻两条线段的 y 坐标之差。求出长的过程就较复杂了。

我们先将原矩形的两个长分为入边和出边：下面的入边、上面的是出边。按 y 坐标排序后遍历，遇到入边就将这段范围在横轴的对应区间的权值加上 1，遇到出边就将这段范围的权值减去 1，这样每个矩形的长就是横轴上权值大于 0 的权值数，离散化后用线段树维护。

8.5 P1856 [IOI 1998][USACO5.5] 矩形周长 Picture

矩形周长并模板题。开两颗线段树分别维护横轴与纵轴的边长。每条线段以坐标为第一关键字，以出入边（入边大于出边）为第二关键字排序，遍历每条边，先更新：遇到入边就将这段范围在横轴的对应区间的权值加上 1，遇到出边就将这段范围的权值减去 1。每条边对答案的贡献为当前横轴上权值大于 0 的权值数 减去 上一条边横轴上权值大于 0 的权值数 的绝对值（因为会涉及到重复贡献，可参考上一题图）。

8.5 P13567 「CZOI-R5」折跃点

题解

8.6 P3380 【模板】树套树

树状数组套权值线段树。这样每次操作都只需要操作 O(\log n) 颗主席树。先离散化。操作 1 和操作 2 可通过线段树二分解决；操作 3 就按修改树状数组的方法修改对应主席树即可；操作 4 求出 k 的排名减 1 即可，如果 k 的排名为 1 则不存在前驱；操作 5 求出 k 的排名后以此为左端点，区间长为右端点二分答案的排名即可，如果最终没二分到任何值就说明没有后继。

8.7 P3810 【模板】三维偏序（陌上花开）

先将每个元素以 a 为第一关键字、b 为第二关键字、c 为第三关键字排序。这样对于第 i 个元素，f(i)=\sum_{j=1}^{i-1}[b_j\le b_i \land c_j\le c_i]。把 (b,c) 看作二维平面上的一个点，这样就转变为了带修二维数点问题：问 (1,1) 到 (b_i,c_i) 的矩形内有多少个点，并插入点 (b_i,c_i)。树状数组套权值线段树维护即可。

注意重复的点的处理。

8.8 P4587 [FJOI2016] 神秘数

先考虑整个序列怎么做。先对序列升序排序，设当前可表示的区间为 [1,y]，要考虑的数为 a，则：如果 a \le y+1，则 a 是可插入的，更新值域为 [1,y+a]；否则 y+1 即为奇妙数。

考虑优化此过程。设当前用值域在 [1,x] 的数表示出的值域区间为 [1,y]，则我们考虑增加在 [1,y+1] 内的任何数字都不会产生神秘数，因为我们已经把 [1,x] 内的数字考虑到了，所以我们可以把在 [x+1,y+1] 的数都考虑进去，设这些数的和为 sum，则当前使用了的值域范围为 [1,y+1]，表示出的值域区间为 [1,y+sum]。这样的时间复杂度是 O(\log \sum a_i) 的（我不会证）。所以我们需要求某个区间内值域在某个区间的数的个数（二维数点），使用主席树维护即可。

8.11 P3369 【模板】普通平衡树

呕。

二叉查找树（BST）是一个满足以下特征的二叉树：

1. 每个节点有一个可比的键值。

2. 任意节点的键值比它左子树的所有节点的键值都大，比它右子树的所有节点的键值都小。以任意一个节点为根的子树都是一颗 BST。

BST 的建树过程为：每插入一个节点，如果其键值小于当前子树的根节点的键值，就往左子树递归，否则往右子树递归。如果遇到了空节点，就插到这个空位上。从此过程可知：BST 的形态由其插入的顺序有关。这直接影响了 BST 的好坏：可能退化成一条链，这样查询某个节点就需要走 O(n) 层；也可能是一颗满二叉树，这样查询某个节点就需要走 O(\log n) 层。

所以平衡树解决的就是维护一颗“平衡”的二叉查找树的问题。

替罪羊树

没用。

最暴力的平衡树，主要思路是：如果发现某棵子树不平衡了，就拍平，重建成一颗平衡的树。其中不平衡的通过不平衡率来判定，具体来说，如果某个子树的大小 乘 不平衡率 小于 其两个子树中某个的大小，则称此子树为“不平衡的”，此时按照子树中序遍历来重建，对于每个节点取序列的中点作为键值。

插入与普通 BST 相同，删除时只标记此点删除，并更新子树大小。在插入删除之后判断子树是否不平衡。使用了一个栈来储存可以使用的节点，以循环使用。

对于查询排名，如果遍历到空节点，返回 1。否则如果 x 小于等于当前节点的键值，就向左递归；否则加上当前节点左子树大小再加 1，向右子树递归。

对于查询第 x 小，如果 x 等于 当前节点左子树大小加 1，返回当前节点的键值。否则如果 x 小于等于当前节点左子树大小，就向左递归；否则将 x 减去当前节点左子树大小再减 1，向右子树递归。

查询前驱相当于查询排名为 x 的排名减 1 的数；查询后继相当于查询排名为 x+1 的排名的数。

Treap

真神。

Treap = Tree + Heap，树堆，即树与堆的结合。Treap 上每个节点除了有一个键值以外还有一个优先级，对于键值，这颗树是一个 BST；对于优先级，这棵树是一个堆（此节点的优先级比左右儿子的优先级都大或小，即大根堆或小根堆，下文按小根堆说明）。如果 Treap 的键值和优先级都确定了，则 Treap 的形态是唯一的。但是我们通常需要动态地操作，做法是对新增节点随机分配优先级，动态调整 Treap 形态，这有两种方法。

旋转 Treap

普通。

旋转 Treap 主要依赖两种操作来调整形态：左旋和右旋，如下图：

对于插入操作，先将要插入的节点按键值放到对应位置，然后为其分配优先级，自底向上调整，如果当前节点的优先级比某个儿子小，就旋转（左儿子比它小就右旋反之左旋）。

对于删除操作，如果删除的节点是叶子，直接删，如果只有一个儿子，就让儿子继承它。否则朝优先级更小的儿子旋转，直到要删除的节点没有两个儿子，就可以直接如上所述删了。其余操作与替罪羊树做法相同。

FHQ Treap

神中神。

FHQ Treap 只用了分裂和合并两种基本操作。

分裂指将一颗 Treap 按照某个固定的键值或排名 x 分为键值或排名都小于等于 x 的子树和键值或排名都大于 x 的子树。合并指将两颗 Treap 按照优先级合并为一棵 Treap，合并操作有一个条件：两棵子树其中一颗中的键值都要小于另一颗。

对于插入操作，将原 Treap 按 x 分裂为两棵子树，然后再新增一个节点，键值为 x，作为另一棵子树，再将这三者合并。

对于删除操作，将原 Treap 按 x 分裂为两棵子树 L 和 R，再将 L 按 x-1 分裂为 LL 和 LR，合并 LR 左右子树，再将其与 LL 合并，再将其与 R 合并。

对于查询排名，可以将原 Treap 按 x 分裂为两棵子树 L 和 R，x 的排名即为 L 的大小加 1，再合并两树；对于查询第 x 小，使用与替罪羊树相同的方法查。

对于前驱，可以将原 Treap 按 x-1 分裂为两棵子树 L 和 R，x 的前驱即为 L 中的最大值，即 L 中第 L 的大小 小的数，使用查询第 x 小函数即可，再合并两树；对于后继，可以将原 Treap 按 x 分裂为两棵子树 L 和 R，x 的后继即为 R 中的最小值，即 L 中第 1 小的数，使用查询第 x 小函数即可，再合并两树。

注意后四种操作需要预先记录答案再合并两树，否则直接 return 就没法合并了。

Splay

鸽了。

8.11 P4008 [NOI2003] 文本编辑器

维护光标位置，采用按排名分裂的 FHQ Treap 解决，这样就能分裂出原文本中连续的一段了，因为 BST 的中序遍历即为原序列，所以输出就直接中序遍历即可。

8.11 P3391 【模板】文艺平衡树

依旧采用按排名分裂的 FHQ Treap，对于区间反转，就在平衡树上打标记，并在合并分裂时下传即可。输出按中序遍历平衡树即可，输出记得下传标记。

8.12 P3835 【模板】可持久化平衡树

由于 FHQ Treap 的分裂和合并操作所修改的节点较少，所以可以使用 FHQ Treap 进行可持久化。因为合并之前一定会分裂，所以只需要在分裂时新开节点即可，合并操作可以不开。

8.12 P5055 【模板】可持久化文艺平衡树

需要在可持久化平衡树基础上再打标记，唯一需要注意的是在下传标记时要新开节点，保证不修改之前的节点。

8.13 P2048 [NOI2010] 超级钢琴

考虑贪心，我们每次选择当前和最大的子段加入答案后删除，选 k 次即可得到答案。设 f(i,l,r) 为当左端点为 i，右端点在区间 [l,r] 内时，子段的最大和，设 sum 为前缀和数组，则 f(i,l,r) = \max_{j=l}^r sum_j-sum_{i-1}，因为 sum_{i-1} 是固定的，所以只需最大化 sum_j 即可，这是一个静态 RMQ 问题，可用 st 表解决。

我们可以开一个大根堆，初始对于每个 i \le n-L+1，将 f(i,i+L-1,\min(n,i+R-1)) 放进堆中。之后循环 k 次，每次取出堆顶计算子段和，然后删除堆顶，我们设堆顶的子段和的左端点为 x，右端点为 y，则将 f(x,x+L-1,y-1) 和 f(x,y+1,x+R-1) 放进堆中。

8.14 P4735 最大异或和

可持久化 Trie 模板题，与可持久化线段树类似（01-Trie 本质就是一种特殊的权值线段树）。插入操作参考可持久化线段树，从高到低位插入，以方便查询；查询操作可转换为找到一个 l-1 \le p \le r-1 使得 sum_{p-1} \oplus sum_{n} \oplus x 最大，其中 sum 为前缀异或和。

因为 sum_n \oplus x 为定值，所以转换为查询一个在某个区间的数使得其异或一个已知的数的值最大。考虑贪心，从高向低位考虑，对于第 i 位，如果存在一个数使得这个数第 i 位与 sum_n \oplus x 的第 i 位不同，则答案的第 i 位为 1，否则为 0，继续向下递归。对每个前缀建树，维护一下树上每个点出现的次数，区间内树上某个点出现次数就是第 r-1 棵树上出现的次数减去第 l-2 棵树上出现的次数。

但是如果 l=1 的话 l-2 就是负数了。不能简单地令 l-2 与 0 取 \max。正确做法是在第 0 棵树上插入 0，这样第 0 棵树的根为 1，查询时就以 0 作为“第 -1 棵树”的根。

8.14 P5283 [十二省联考 2019] 异或粽子

P2048 [NOI2010] 超级钢琴 的异或版，不妨采用与之相同的策略，唯一不同的是 f(i,l,r) 为当左端点为 i，右端点在区间 [l,r] 内时，子段的最大异或和，设 sum 为前缀异或和数组，则 f(i,l,r) = \max_{j=l}^r sum_j \oplus sum_{i-1}。由于 sum_{i-1} 是固定的，所以转变为了查询一个在某个区间的数使得其异或一个已知的数的值最大，这就是 P4735 最大异或和，使用可持久化 Trie 解决即可，并在每个数字所代表的 Trie 上的链的叶子节点打上标记（设为 a），表示这个叶子节点到根的路径上表示的是 sum_a，这样就能求出堆顶的子段异或和的右端点了。

8.14 P6623 [省选联考 2020 A 卷] 树

01-Trie 好题。以下定义 (v_c+d(c,x)) 为一项，注意到节点 u 的价值为其所有子节点的价值中每一项加 1 后异或起来再异或 v_u，因为子节点价值中的每一项对应到其父节点只有 d(c,x) 加了 1。

所以我们不妨从下向上计算，我们对每个节点开一个 Trie 存此节点的价值的每一项，此 Trie 需要支持：插入、合并、全局加 1、求全局异或和，这些操作都可以直接维护。

8.16 P4391 [BalticOI 2009] Radio Transmission 无线传输

KMP 的 Border 有一个性质：设 n 为字符串的长度，k 为某个 Border 的长度，则 n-k 是原串的一个周期的长度，因为本题要最小化周期长度，所以要最大化 Border，即 n-nxt_n。

8.18 P3435 [POI 2006] OKR-Periods of Words

依旧使用上一题所说的性质，但这次我们需要最大化周期，即最小化 Border 长度（大于 0）。我们对于每一个前缀可以递归 nxt 数组（nxt_i,nxt_{nxt_i},\dots）直到 0，但这样会 TLE。我们可以将前面记录下来的答案再记到 nxt 数组里以解决 TLE。

8.19 P5537 【XR-3】系统设计

因为一个点到根节点的路径是唯一的，所以我们可以用一个序列 b 来描述这个点（称其为路径序列），即：先从根节点走到其编号 b_1 小的孩子、再从这个节点走到其 b_2 小的儿子……这样问题就转换为了询问一个最长的 x 点的路径序列再拼上 a_l \sim a_r 某个前缀序列组成的路径序列使得此路径序列为某个节点的路径序列。

我们可以用哈希来判断是否存在，并且这个问题也是满足单调性的，所以我们可以二分解决。因为还涉及单点修改需要用线段树维护一下。

8.20 AT_arc060_d [ARC060F] 最良表現

题解

8.21 P3546 [POI 2012] PRE-Prefixuffix

以下记 s[i,j] 表示 s_is_{i+1}\dots s_j。

如果两个字符串 s_1,s_2 是循环相同的，则一定存在两个字符串 A,B 使得 s_1=AB,s_2=BA。所以我们可以把原字符串看成：ABCBA 的形式，而我们需要最大化 AB。

我们可以枚举右回文串的中心。开两个 set，第一个记录每个满足 s_i=\texttt{\#} 的 i 的 i+\frac{p_{i}-1}{2} 和其对应的 i，第二个记录所有满足第二条的 i。每次从第一个 set 找到所有不满足第二条的 i 在两个 set 里面删去。然后在第二个 set 里面二分找到最小的 mid（这样能满足第四条），就能计算以当前点为右回文串的中心时的最长双倍回文了。

以上是暑假刷题记录，以下均为 25.9 开学后的刷题记录。

9.2 P2444 [POI 2000] 病毒

先对代码建立 AC 自动机。因为所求的代码为无限长的，所以它一定有循环，我们考虑某个答案在此 AC 自动机上匹配的过程，一定是从 0 出发之后在某个点进入循环，然后就一直重复循环，于是问题就转换为了在 AC 自动机上（不包括 fail 指针）找到一个环，满足以下条件：

1. 它和 0 联通。

2. 环上每个点到 0 的路径组成的字符串没出现过任何一个给出字符串。

对于第一条，跑 dfs 即可；对于第二条，相当于环上每个点不在任何一个给出字符串在 AC 自动机上位置的 fail 子树里面，于是用树状数组给整个子树打标记即可。

9.2 CF163E e-Government

“带修”的 AC 自动机。普通的 AC 自动机匹配方法是对于每个 AC 自动机的节点向上一直跳 fail，所以在不改变 AC 自动机形态的情况下增加一个字符串将相当于将它的 fail 子树内的所有节点都加 1，减去同理。于是用树状数组维护每个节点的出现次数，修改就是子树加减，匹配就是单点查询。

9.2 CF1202E You Are Given Some Strings...

考虑枚举断点，对于断点 i，此处的答案可看作所有 s 中满足是 t[1,i] 的后缀的数量 乘 s 中满足是 t[i+1,|t|] 的前缀的数量，我们建立正串和反串两个 AC 自动机，前者可以预处理上式的前一项，后者可以预处理上式的后一项，在 build 时顺便从 fail 转移即可。

9.3 P4045 [JSOI2009] 密码

AC 自动机上 dp。我们设 f[i][j][k] 表示目前考虑到答案的第 i 位，且当前在 AC 自动机的 j 号节点上，且当前已经含有字符串的情况为 k（状压）时的方案数，则有转移：f[i][j][k] \rightarrow f[i+1][son[j][c]][k|ed[son[j][c]]] 其中 0\le c\le 25，son[j][c] 表示 j 的第 c 个子节点，ed[son[j][c]] 表示从 son[j][c] 到根的字符串中有包含的给出的字符串的种类数（状压）。

输出方案就暴搜。

9.6 P2292 [HNOI2004] L 语言

依旧 AC 自动机上 dp。我们先考虑一个朴素的 dp：设 f_i 表示长度为 i 的前缀是否可行，则我们转移时暴力跳 fail 即可，但这样会超时。

注意到 1\le |s| \le 20，我们考虑状压。设 f_i 表示有长度为哪些的 s 是在 AC 自动机上的 i 号节点表示字符串的后缀，默认 f_0=1，这个可以在构建适配指针时在失配树上计算得到。然后我们在 AC 自动机上遍历 t，设当前遍历到的节点为 p，当前长度为 i。用一个变量 v 状压地记录长度在 [i-1,i-20] 的 t 的前缀中，有哪些长度是可以被理解的，如果 v\&f_p 大于 0，说明当前长度可以从某个之前的长度转移来，更新 v|=1，每次遍历都将 v<<1，利用自然溢出方便一点。

9.6 CF86C Genetic engineering

题解

9.10 P2151 [SDOI2009] HH 去散步

如果没有“不会立刻沿着刚刚走来的路走回”的限制就是一个裸的邻接矩阵幂。对于这条限制，我们不妨将一条双向边拆成两个单向边，再将这两个单向边看作两个点，把有公共点的边所对应的点相连，并且不连由一条无向边拆成的两条边所代表的点。再计算此邻接矩阵的 t-1 次幂即可（因为需要正好走 t 个点，就需要走 t-1 条边）。

9.10 P6569 [NOI Online #3 提高组] 魔法值

我们定义此处的矩阵乘法为：C_{i,j}=\oplus_{k=1}^m A_{i,k}\times B_{k,j}，则第 a 天时的魔法值可表示为 F \times E^a，其中 E 为邻接矩阵，F=\begin{bmatrix} f_{1,0} & f_{2,0} & \dots & f_{n,0}\end{bmatrix}。但如果使用普通的矩阵快速幂时间复杂度为 O(qn^3\log a) 的，会超时。我们注意到向量与矩阵相乘的时间复杂度并非 O(n^3) 而是 O(n^2) 的，于是可以预处理所有 E^{2^k} 的矩阵，再进行矩阵快速幂，每次都将 F \times E^{2^k}，这样总时间复杂度为 O(qn^2\log a)。

9.13 P6772 [NOI2020] 美食家

先考虑一个简化简化版本：不考虑美食节且 w=1。我们定义此处的矩阵乘法为：C_{i,j}=\max_{k=1}^n A_{i,k}+B_{k,j}，则此时邻接矩阵 E 的 k 次幂代表任意两点之间恰好走 k 条边的路径中边权和的最大值。我们将点权下放到以此点为终点的边上（如果两点不连通就设为 -\inf），设 F=\begin{bmatrix} c_1 & -\inf & \dots & -\inf \end{bmatrix}，则 F=F \times E^T 即为从点 1 到每个点恰好走 T 条边的路径中点权和的最大值，用矩阵快速幂计算即可。

如果 w\le 5，处理方式是对每个把每个点分裂成 5 个点，第 i 个与第 i+1 个之间连边，边权为 0，这样对于一条边 (u,v,w) 就从 u 的第 w 个点，向 v 的第 1 个点连边。这样边权为 w 就转换为了走 w 条边。

如果加入美食节，就把走 T 条边分成 k 段，每段分别计算，如果 F_x>c_1，则令 F_x=F_x+y，因为 F_x=c_1 就意味着 1 到 x 中没有恰走 t 条边的路径。但这样会超时，我们可以预处理 E^{2^k}，则这样矩阵快速幂的时间复杂度因为是向量乘矩阵所以会优化掉一个 n。

注意 E_{i,i}=-\inf 而非 0，因为题目要求不能在任何城市停留。

9.21 P2447 [SDOI2010] 外星千足虫

高斯消元求解异或线性方程组。普通的高斯消元时间复杂度为 O(n^2m) 的，在此题无法通过，注意到增广矩阵中只有 0 和 1，因此可以使用 bitset 进行优化，时间复杂度优化到 O(\frac{n^2m}{w})，其中 w=32，可以通过。至于求出最少需要前几个方程组，求解异或线性方程组记录下 mx（当前列第一个系数等于 1 的位置）的最大值即可。

9.21 P2973 [USACO10HOL] Driving Out the Piggies G

我好像理解期望了。设 f_i 表示炸弹期望经过点 i 的次数，则炸弹在点 i 的爆炸概率为 f_i \times \frac{p}{q}，我们有一下转移：

其中 d_j 表示点 j 的出度。

但是这个方程不能直接转移（因为它是有后效性的），于是使用高斯消元解决。

说说我对期望的理解吧。考虑这个问题：有一个硬币，如果抛到正面朝上则获得 2 元并继续投掷，否则结束投掷，问期望获得多少元。我们设期望得到 x 元，则能得到此式子：x=\frac{1}{2} \times 0 + \frac{1}{2}(x+2)，我们把这里的等于号看作赋值的意义，则我们可以看作递归地定义了 x（每次可以将原式带入等式右边）。然后我们在把等于看作等量关系的意义，就可以解出此方程：x=2，所以期望得到 2 元。

9.23 P3232 [HNOI2013] 游走

一个贪心的想法是按边期望做过的次数排序，贪心地编号，但是边数过多，无法通过高斯消元求解出，于是转换为点的期望经过次数。

具体地，设点 i 期望经过 f_i 次，其度数为 d_i，边 (u,v) 期望经过 g_{(u,v)} 次，则有：

不包含点 n 是因为到达点 n 就不能再走了，同时我们也不用计算 f_n 了，我们根据 f 的递推式列出 n-1 个方程，然后解方程即可得到 f 进而得到 g，然后贪心编号即可。

9.25 P3211 [HNOI2011] XOR和路径

由于小数不能异或，所以我们考虑按位处理，我们设 f_i 表示从 i 到 n 的路径中（不设为 1 到 i 是因为无法界定到点 i 后能否继续走）这一位为 1 的概率，则答案即为（注意这里的 f_1 指的不是同一个）：

转移式即为：

并且 f_n=0，然后用高斯消元解即可。

9.27 P4869 albus就是要第一个出场

转换一下题意，就是求不去重的异或值排名。

如果去重，即在线性基里查排名很简单：对数字进行二进制拆分，然后找线性基里位数等于每个 1 的位数的值根据它在线性基里的位置累加贡献即可。

这道题目的关键在于这么一个结论：对于一个长度为 n 的序列 A，设其线性基为 S，其大小为 m，则 B 中每个数出现的次数均为 2^{n-m}，证明如下：

证明这个问题，实际上等价于证明 0 在 B 中的出现次数为 2^{n-m}，因为 0 是异或的单位元。

查询操作可用二维前缀和，简化为四个以 (1,1) 为左上角的矩阵和，于是我们的问题就简化为对任意 k、l 快速求出：\sum_{x=1}^k \sum_{y=1}^l A_{x,y}。于是：

观察到 D_{i,j} 出现次数为 (k-i+1)(l-j+1)，则有：

然后用二维树状数组维护 D_{x,y}、xD_{x,y}、yD_{x,y}、xyD_{x,y} 即可。

10.5 P5656 【模板】二元一次不定方程 (exgcd)

exgcd 可以求出 ax+by=\gcd(a,b) 的一组解。具体来说，因为 \gcd(a,b)=\gcd(b,a \bmod b)，因此假设我们求出来了 bx'+(a \bmod b)y'=\gcd(b,a \bmod b) 的一组解 x',y'，则有：

于是对于原方程组就有：x=y',y=x'-\lfloor \frac{a}{b} \rfloor y'。

递归求解即可，边界为 b=0，此时 x=1,y=0。

得到 ax+by=\gcd(a,b) 的一组解 x_0,y_0 后在等式两边同时乘上 \frac{c}{\gcd(a,b)} 就可以得到 ax+by=c 的一组解：x=\frac{c}{\gcd(a,b)}x_0,y=\frac{c}{\gcd(a,b)}y_0。

接下来考虑求出原方程的通解，我们在等式左边加上再减去 s，得：(ax+s)+(by-s)=c，即：a(x+\frac{s}{a})+b(y-\frac{s}{b})=c，则此时一组解为 x'=x+\frac{s}{a},y'=y-\frac{s}{b}。因为 (x+\frac{s}{a}),(y-\frac{s}{b}) 为整数且 x,y 为整数，所以 \frac{s}{a},\frac{s}{b} 为整数，所以 a \mid s 且 a \mid s，即 \operatorname{lcm}(a,b) \mid s，设 \operatorname{lcm}(a,b)=l，则 s=kl，将其带入 x'=x+\frac{s}{a} 得：

同理可得 y'=y-\frac{ka}{\gcd(a,b)}，设 d_x=\frac{b}{\gcd(a,b)},dy=\frac{a}{\gcd(a,b)}，则通解形式为：

根据裴属定理，可知 ax+by=c 有解的充要条件是 \gcd(a,b) \mid c，因此如果 \gcd(a,b) \nmid c 则无解。

如果有正整数解，则：

解得：-\frac{x}{dx}<k<\frac{y}{d_y}，即：\lceil \frac{1-x}{dx}\rceil \le k \le \lfloor \frac{y-1}{d_y} \rfloor，注意左边减去 1，右边加上 1 的原因是需要考虑到 d_x \mid x 与 d_y \mid y 的情况。

于是有正整数解就需要满足 \lceil \frac{1-x}{dx}\rceil \le \lfloor \frac{y-1}{d_y} \rfloor，解的数量即 k 的数量，根据通解形式可得 x 的最小值、y 的最大值在 k 取最小值时得到，x 的最大值、y 的最小值在 k 取最大值时得到。

否则无解，此时 k 取最小值时 x 最小，k 取最大值时 y 最小。

10.6 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

每个方程组形如 x\equiv b_i ~~(\bmod ~a_i)。

我们设 A=\prod_{i=1}^n a_i，m_i=\frac{A}{a_i}，m_i^{-1} 为 m_i 在模 a_i 意义下的逆元，则原方程组的最小解为：x=\sum_{i=1}^n b_im_im_i^{-1} \ (\bmod \ A)。

证明很简单：因为 \forall j \neq i, a_i \mid m_jm_j^{-1} 于是有：

注意普通 CRT 只能解决 a_i 互质的情况。

10.6 P4777 【模板】扩展中国剩余定理（EXCRT）

CRT 求解同余方程组要求 a_i 互质，但 EXCRT 不用保证；CRT 是构造解，而 EXCRT 是对方程组进行合并。

我们假设有两个方程：

可得：x=Ax'+B=ay'+b，即：Ax'-ay'=b-B，由裴属定理可知当 \gcd(A,a) \nmid (b-B) 时，原方程组无解。

如果有解，因为我们只需要用 x',y' 中的一个即可还原 x，因此我们不妨将原方程变为：Ax'+ay'=b-B，只考虑 x'。可以用 exgcd 求出 Ax'+ay'=\gcd(A,a) 一组解，再将其乘上 \frac{b-B}{\gcd(A,a)} 即可得到 Ax'+ay'=b-B 的一组解 x_0,y_0，则通解形式为：

将 x'=x_0+k\frac{a}{\gcd(A,a)} 带入 x=Ax'+B 得：

即：

至此，我们就将两个方程组合并为了一个。

10.9 P10499 开关问题

构造以下异或方程组：

其中 a_{i,j}=1 表示如果操作 j，i 也会相应改变。

10.9 P3164 [CQOI2014] 和谐矩阵

我们可以对于每个 (i,j) 构造形如 x_{i,j} \oplus x_{i+1,j} \oplus x_{i-1,j} \oplus x_{i,j-1} \oplus x_{i,j+1}=0 的方程。列出这样的 n \times m 个方程组成方程组后解方程即可。然而这样只会出来全 0 矩阵，我们不妨将所有自由元设为 1，然后在改变其他方程组。

10.12 P3750 [六省联考 2017] 分手是祝愿

首先某个局面的最优操作方法一定是从后向前依此关灯，因为关掉前面的灯无法改变其后面的灯的状态。设 f_i 表示当前最优需要操作 i 次时，把所有灯都关上的期望次数，则有：

如果直接用高斯消元会超时，观察到这个系数矩阵是一个三对角线矩阵（每个方程只涉及到 f_i,f_{i-1},f_{i+1}），可以模拟高斯消元来做。还有一种做法是令 d_i=f_i-f_{i-1}，则有：

于是 d_i 可递推得到，进而递推得到 f_i。

10.15 P5664 [CSP-S2019] Emiya 家今天的饭

直接考虑“每种主要食材至多在一半的菜中被使用”需要记录每种食材的出现次数，很难。正难则反，原问题等价于：总方案数 减去 有出现在超过一半的菜中被使用的主要食材（以下简记为众食材）的方案数。

先考虑前者。设 g_{i,j} 表示从前 i 行选取 j 道菜的总方案数，s_i=\sum_{j=1}^m a_{i,j}，则有：g_{i,j}=g_{i-1,j}+g_{i-1,j-1} \times s_i，总方案数即为 \sum_{i=1}^n g_{n,i}。

再考虑后者。因为众食材做多只有 1 种，因此不妨枚举这个众食材，设众食材为第 x 种主要食材，设 f_{i,j,k} 表示在前 i 行选了 j 道众食材、选了 k 道其余食材的方案数，则有：f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k} \times a_{i,x} + f_{i-1,j,k-1} \times (s_i-a_{i,x})，出现众食材 x 的方案数即为 \sum_{j=1}^n \sum_{k=1}^{j-1} f_{n,j,k}，这样的时间复杂度为 O(n^3m)，会超时，考虑优化。

我们发现最终只会考虑 j>k 即 j-k>0 的 f，因此不妨设 l=j-k，令 f_{i,l} 表示考虑前 i 行，且 j-k=l 时的方案数，则有：f_{i,l}=f_{i-1,l}+f_{i-1,l-1} \times a_{i,x} + f_{i,l+1} \times (s_i-a_{i,x})，出现众食材 x 的方案数即为 \sum_{l=1}^n f_{n,l}，将所有的 x 累加即可得到有出现众食材的方案数。时间复杂度为 O(n^2m)，可以通过。注意 l 的范围为 -n \le l \le n，因此要将数组下标加上 n。

10.18 P7077 [CSP-S 2020] 函数调用

在一个函数被调用之后，如果又将所有数乘上了 mul 倍，则可以看作这个函数执行了 mul 次，则我们可以设 f_i 表示 i 号函数的执行次数，因为乘上一个数影响的是之前的数字，因此我们不妨倒序处理。

先用一遍 dfs 求出 mul_i，其表示调用 i 号函数后整体会被乘上 mul_i 倍，维护 Mul 表示当前总共被乘上了多少倍，初始 Mul=1。之后倒序遍历每个操作，设当前调用的函数为 x：

• 如果当前操作为 1 类函数，则 f_x \leftarrow f_x+Mul。
• 如果当前操作为 2 类函数，则 Mul \leftarrow Mul \times V_x，f_x=1。
• 如果当前操作为 3 类函数，则 f_x \leftarrow f_x+Mul，Mul \leftarrow Mul \times mul_x。

之后就不需要再考虑操作顺序的问题了，因为这一步本质上就是将形如 ((x_i+a_1)\times b_1 + a_2) \times b_2 \dots 的式子拆成了 x_i+a_1b_1b_2\dots+a_2b_2\dots+ \dots，每一个操作的函数的执行次数已经求出，之间相互独立。

我们把图建出来，很明显是一个 DAG，之后我们用拓扑排序将这些 f 下传。我们只需要考虑 3 类函数，设其编号为 i，维护当前其所调用的函数当应增加的操作次数 t，初始 t=f_i，依旧倒序遍历其所调用的函数，设其编号为 j：

• 如果当前函数为 1 类函数，则 f_j \leftarrow f_j+t。
• 如果当前函数为 2 类函数，则 t \leftarrow t \times mul_j。
• 如果当前函数为 3 类函数，则 f_j \leftarrow f_j+t，t \leftarrow t \times mul_j。

最后让 a_i 先乘上 Mul，再加上 f_i \times V_i，即可。

10.18 P14255 列车（train）

题解

10.19 P14254 分割（divide）

越发觉得自己菜。首先能观察到只能选同一层的结点，因为有 b 深度单调不升的性质，所以 b_1 的深度一定是最浅的之一，如果选了一个比它深的结点，则显然一定不能满足 S_1 是其余集合的交集的条件。

然后就简单了。因为只能选同一层的结点，所以 \exists i,S_1=S_i 且 \forall i,S_1 \subset S_i。因为 S 一定是一段连续的区间，所以我们不妨预处理 d_i 表示 i 的深度，mxd_i 表示以 i 为根的子树的最大深度。则上条件就等价于 \exists i,mxd_{b_1}=mxd_{b_i} 且 \forall i,mxd_{b_1} \le mxd_{b_i}。我们枚举 b_1，设满足 mxd_{b_1} \le mxd_{b_i} 且 d_{b_1}=d_{b_i} 的 i 有 sum 个，满足 mxd_{b_1} = mxd_{b_i} 且 d_{b_1}=d_{b_i} 的 i 有 cnt 个，则有：

可以通过将相同深度的结点存到一起然后按照 mxd 排序的方式快速计算 sum，用 map 快速计算 cnt。

10.19 P11233 [CSP-S 2024] 染色

不妨设 f_{i,0/1} 表示考虑到 A_i，其中 A_i 染成 0/1 时的最大得分。

首先，如果这一位无贡献，则 f_{i,0}=f_{i,1}=\max(f_{i-1,0},f_{i-1,1})。

否则，以 f_{i,0} 为例，则对于一个 j < i 使得 A_j=A_i，其染色的形式一定为：A_j 和 A_i 的颜色为 0，A_{j+1} \sim A_{i-1} 的为 1。实际上我们只需要考虑最大的 j，因为对于其余的 j，在 A_{j+1} \sim A_{i-1} 中把与 A_{i} 相等的 A 也染成 0 是更优的。接下来考虑如何计算贡献，可拆分成 3 部分：

特殊情况是 A_i=A_{i-1}，显然贡献为 f_{i-1,0}+A_i，特判即可。

于是将无贡献可有贡献取 \max 即可。

10.24 P14279 [ROI 2014 Day2] 乌拉尔高速公路

题解

10.26 P1600 [NOIP 2016 提高组] 天天爱跑步

对于一条 s \rightarrow t 的路径，不妨按照 \operatorname{lca}(s,t)（以下简记为 l）将其拆成两段：s \rightarrow l 和 l \rightarrow t 分别考虑，因为这样的两个路径的结点深度有规律可循。

对于 s \rightarrow l，我们设这条路经上有一个点 x，则需要满足 s \rightarrow x 的路径长度等于 w_x，即 dep_s-dep_x=w_x，即 dep_s=dep_x+w_x。

对于 l \rightarrow t，我们设这条路经上有一个点 y，此时 s \rightarrow y 的路径长度等于 dep_s-dep_l+dep_y-dep_l=dep_s+dep_y-2dep_l，即 dep_s+dep_y-2dep_l=w_y，即 dep_s-2dep_l=w_y-dep_y。

综上，我们对每个结点开两颗动态开点的权值线段树分别记录如上的 dep_s 和 dep_s-2dep_l 的出现次数，然后用树上差分标记，再线段树合并解决。

10.27 P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds

以后组合数用大括号表示：C_n^m=\binom{n}{m}。

首先因为操作 1 免费，于是我们可将问题转化为对于任意有 x=\lceil \frac{n}{2}\rceil 个 1，y=\lfloor\frac{n}{2}\rfloor 个 0 的 01 序列，最少执行多少次将相邻两位取反的操作才能使序列每个数都相等。而这样的 01 序列共有 \binom{n}{x} 种，每种对应原序列有 x!y! 种，因此答案要乘上 x!y!。

• 放一个 c \le j+1 的数字，再枚举 l 去填之前的：

  f_{i,j,k} \times (sum_{j+1}-(i-k)-l) \times \binom{k}{l} \binom{cnt_{j+1}}{l}l! \rightarrow f_{i+1,j+1,k-l}

• 放一个 c > j+1 的数字作为一个新的空位延后计算贡献，再枚举 l 去填之前的：

  f_{i,j,k} \times \binom{k}{l} \binom{cnt_{j+1}}{l}l! \rightarrow f_{i+1,j+1,k-l+1}

最后 \sum_{i=0}^{n-m} f_{n,i,n-sum_i} \times (n-sum_i)! 即为答案，因为 \sum_i cnt_i=n，因此总时间复杂度为 O(n^3)。

11.10 P7518 [省选联考 2021 A/B 卷] 宝石

先根据 P 的顺序为宝石重新编号。对于一条 s \rightarrow t 的路径，可以将其分成 s \rightarrow \operatorname{lca}(s,t) 和 \operatorname{lca}(s,t) \rightarrow t 两段。对于前一段，预处理点 x 最近的满足 w_y=1 的祖先和最近的满足 w_y=w_x+1 的祖先，然后倍增即可。对于后一段，二分答案，对于一个颜色 c，用主席树维护找到从 t 向上的第一个满足 w_u=c 的祖先 u。预处理点 x 最近的满足 w_y=w_x-1 的祖先，然后从 u 倍增验证是否可行即可。

11.11 P2680 [NOIP 2015 提高组] 运输计划

原题等价于一棵树上给定一些路径问免去一条边的权值后路径权值和的最大值最小是多少。考虑二分答案，对于一个答案 mid，需要免去权值的边需要满足其被所有权值和大于 mid 的路径经过；其边权大于等于路径权值和的最大值减去 mid。于是我们需要处理出所有路径的权值和，使用倍增结合 lca 即可；还需要使用树上倍增快速在二分时处理出每条边被路径经过的次数。

11.12 P2597 [ZJOI2012] 灾难

考虑如何刻画这个灾难值，我们不妨构建这样一颗树，每个节点的父节点为原 DAG 中最近的能使其消灭的点，这样统计子树大小即可得到答案。而对于结点 i，其父节点即为树中的 \operatorname{lca}\{ a_i\}。于是我们拓扑排序后这么连边即可，注意这里的 \operatorname{lca} 需要动态维护（动态添加叶子），故只能使用倍增。

11.15 P14507 缺零分治 mexdnc

题解

11.16 P14509 树上求值 tree

题解

11.18 P8867 [NOIP2022] 建造军营

B 国只能摧毁一条边，故在一个边双连通分量里的军营不可能无法到达。所以我们考虑边双缩点，这样就缩成了树。设缩点后的点 i 在原图中包含 x_i 条边、y_i 个点。

然后考虑树形 dp，如果朴素地定义 f_{u,i,j} 表示考虑到以点 u 的前 i 个儿子为根的子树，以点 u 为根的子树有 / 没有军营的方案数，情况太复杂了，拿样例一举例：很难考虑到在城市 2 建军营，不看守这条道路类似的情况。故我们在如上定义增加一条限制：每个军营与点 u 之间的边都必须要看守，就不用考虑这种情况了。

考虑转移，我们直接把第二维滚动：

初始（不考虑任何子树时）有 f_{u,0}=2^{x_u}，f_{u,1}=2^{x_u} \times (2^{y_i}-1)。

然后枚举 u 的儿子 v，则有：

• - 到当前节点之前都没有建造军营，则在当前子树一定要建造军营：$f_{u,1} \leftarrow f_{u,0} \times f_{v,1}$。 - 否则：$f_{u,1} \leftarrow f_{u,1} \times (2f_{v,0}+f_{v,1})$。

考虑统计答案：如上举的例子是军营全在同一个子树内，而这个子树不再往外部连边的情况，故我们可以枚举所有的军营都在以点 i 为根的子树内的情况，然后任意连接除了点 i 子树内的边和点 i 连向其父亲的边（这是因为如果连了那么这些情况也会在它父亲的状态中涵盖）以外的边。设以点 i 为根的子树在原图中共有 t_i 条边，则 ans \leftarrow ans+f_{i,1} \times 2^{m-t_i-1}，特别地，当 i=1 时：ans \leftarrow ans+f_{1,1}。

11.19 P7961 [NOIP2021] 数列

考虑从 S 的角度设计 dp，毕竟这个进位很难处理。设 f_{i,j,x,y} 表示考虑 S 的前 i 位（最低位为第 0 位），确定了 j 个 \{a_i\} 的元素，S 的二进制已经有了 x 个 1，第 i-1 位向第 i 位进位为 y。

从之前的状态转移到 f_{i,j,x,y} 太麻烦了，考虑从 f_{i,j,x,y} 向后转移。第 0 位到第 i-1 位已经在当前状态的讨论范围内了，我们讨论第 i 位，设 \{a_i\} 中有 c 个 i。则此时向第 i 位的进位增加了 c，总共为 y+c，故考虑到第 i 位的 S 有 x+(y+c) \bmod 2 个 1，第 i 位向第 i+1 位的进位为 \lfloor \frac{y+c}{2} \rfloor。综上，f_{i,j,x,y} 向后转移的状态为：

状态转移即为：

统计答案就枚举 x,y，然后判断 S 的二进制中会不会有超过 k 个 1，累加 f_{m+1,n,x,y}。

11.22 P9871 [NOIP2023] 天天爱打卡

考虑 dp，设 f_i 为前 i 天的答案。我们枚举 j 表示第 j \sim i 天都跑步了且 i-j+1 \le k，就有：f_i=\max\{f_{i-1},f_{j-2}-d(i-j+1)+v_{[j,i]}\}，其中 v_{[j,i]} 表示区间 [j,i] 都跑步能提高多少能量，即 v_{[j,i]}=\sum_{i=1}^m [j \le x_i-y_i+1 \wedge x_i \le i]v_i，j-2 是因为第 j-1 天不能跑步。

我们只需要考虑 x_i 和 x_i-y_i+1 处的 f，故离散化，设离散化后的 i 原本是 b_i。对挑战的 x_i 排序，动态加入，这样就只需要考虑 j \le x_i-y_i+1 了。考虑用线段树维护 g_j=f_{lst(j)}-d(i-j+1)+v_{[j,i]}，lst(j) 为第一个 j' 使得 d_j-d_{j'} \ge 2。则从 i \rightarrow i+1 时，所有的 g_j 都要减去 d(b_i-b_{i-1})。加入挑战 p 时就 \forall 1 \le b_j \le x_p-y_p+1,g_j \rightarrow g_j+v_p。每次二分出 f_i 的转移区间 [j,i]，先在线段树中加入 g_i（相当于单点加 f_{lst(i)}-d），然后 f_i=\max\{f_{i-1},\max_{k=j}^i g_k\}。

11.23 CF708C Centroids

根据题目中重心的定义，如果想让点 u 成为重心，就需要从它唯一一个大小大于 \frac{n}{2} 的子树中拿出一个最大的且大小不大于 \frac{n}{2} 的子树接到 u 上，如果这样还有大小大于 \frac{n}{2} 的子树，就无法成为重心，否则可以。

考虑以重心为根 dp，则点 u 大小大于 \frac{n}{2} 的子树一定是除了它的子树之外的那部分（以重心为根时，所有以某点子结点为根的子树大小不大于 \frac{n}{2}），设 f_u 为以点 u 为根的子树外的最大子树，则点 u 可以成为重心的条件为：n-sz_u-f_u \le \frac{n}{2}。设 bro_u 为点 u 所有兄弟结点，则有：

对于中间那一项预处理同深度结点子树大小最大和次大值即可快速求出。

11.24 P5298 [PKUWC2018] Minimax

设 f_{i,j} 为点 i 权值为 j 的概率，则有：

这样是 O(n^2) 的，注意到状态有大量浪费，加上这个前后缀和的形式，考虑线段树合并去优化。先离散化。我们在合并时顺带维护左右两线段树的前缀后缀和（当区间为 [l,r] 时，就维护 [1,l-1] 和 [r+1,n] 的和），如果合并到两颗线段树中有一颗没有节点了，就在另一颗区间乘。如果只有一个子节点，直接继承即可，叶子结点就是单点加。

11.26 CF1100F Ivan and Burgers

线性基区间查询。考虑对每个前缀都维护一个线性基，设 b_i 为第 i 位的值。额外记录 pos_i 表示对第 i 位造成影响的数的编号。查询就从第 r 个线性基中找所有 pos_j\ge l 的位置即可。故我们需要让 pos_i 尽可能大以保证正确：设要插入 x，编号为 i，则如果遇到 pos_j<i 就交换 pos_j 和 i 与 b_j 和 x。

11.29 P14636 [NOIP2025] 清仓甩卖 / sale

题解

12.3 P14638 [NOIP2025] 序列询问 / query

特殊性质 D、E 的所有区间都会过二等分点或四等分点，这启示我们用分治。定义 sol(l,r) 为左右端点都在 [l,r] 且都过中点的区间对答案的贡献，用 f_i 表示。枚举 i \in [l,mid] 为左端点，有：f_i=\max_{j=max(i+L-1,mid+1)}^{min(i+R-1,r)} sum_j-sum_{i-1}，枚举 i \in [mid+1,r] 为右端点，有：f_i=sum_i-\max_{j=max(i-R+1,1)}^{min(i-L+1,mid)} sum_{j-1}，注意判断下标不要超过范围，以及区分 L,R 和 l,r。然后更新 ans_i，递归 sol(l,mid),sol(mid+1,r)。这样单次询问时间复杂度 O(n \log n)，每个区间总会在某一次被计算。

考虑按 L,R 分块，每 [2^k,2^{k+1}) 为一块，O(n\log^2 n) 预处理出来。然后每次询问对于整块就对每个位置 O(1) 取 \max。散块一定满足 2^k \le L' \le R' \le 2^{k+1}，一定有区间内的元素到两端至少一端的距离不大于 L'，故预处理 f_i,g_i 表示以 i 为左 / 右端点的区间最大值，然后 ans_i=\max(\max_{j=max(1,i-L'+1)}^i f_i,\max_{j=i}^{min(n,i+L'-1)} g_i)，单调队列即可。

12.4 CF1009F Dominant Indices

原题相当于求每个点子树中同深度点最多的且深度最小的深度。设 f_{i,j} 表示点 i 子树中与它距离 j 的点有多少个，则有：f_{u,j}=\sum_{v\in son_u} f_{v,j-1}。考虑用长剖优化，对于长链，我们用指针 O(1) 转移，否则暴力，每次需 O(短链长) 的时间复杂度，因为短链长度之和不超过 n，故总时间复杂度 O(n)。

12.6 P4103 [HEOI2014] 大工程

先建虚树，考虑 dp，设 fmn_u,fmx_u 为点 u 子树内与其最近 / 最远的关键点的距离，fsum_u 为点 u 子树内所有关键点到点 u 的距离。我们考虑对于点 u，枚举子节点 v，按顺序考虑贡献，最后考虑 u 自己的贡献。注意要先对答案进行更新在对 dp 数组更新，例如，设代价和为 ans，边 (u,v) 权值为 w，sz_u 为点 u 子树内关键点的数量，则：ans \leftarrow fsum_u\times sz_v+(fsum_v+sz_v\times w)*\times sz_u，之后更新 v 对 dp 的贡献，其余答案同理。

12.7 P4719 【模板】动态 DP

设 f_{i,0/1} 表示考虑以点 i 为根的子树且选 / 不选点 i 的最大权值，不带修的转移为：

发现修改会使一条到根的路径被修改，考虑树链剖分。对转移进行修改，先分离重儿子，设 lson_u 为轻儿子集合，g_{u,0}=\sum_{v\in lson_u} \max(f_{v,0},f_{v,1}),g_{u,1}=a_u+\sum_{v\in lson_u} f_{v,0}，则有：

即：

可用 (\max,+) 矩阵乘法优化，即：

将乘号右边不断递归展开直到叶子的上一层（一条重链的链底一定是叶子节点），然后等号右边就成了叶子结点的 f 值组成的矩阵。会发现对于叶子节点，g,f 的对应值相同，故在实际程序中可以去掉最后乘的这个东西，转化为若干转移矩阵相乘，而 f_{u,0},f_{u,1} 就与相乘后矩阵的第一列对应。

用线段树维护转移矩阵。注意只能是列向量的形式，因为行向量去乘的话它就要放在乘号前面，这样就需要从重链底乘到重链顶，而线段树按 dfs 序操作只能从重链顶乘到重链底。

考虑修改，首先修改 a_x 及 g_{x,1}。之后会发现对于一条重链只需要修改链底即可（只有上一条走到的重链的链顶会作为此处的轻儿子被修改）。我们记录修改前和修改后的上一条走到的重链的链顶的矩阵，根据矩阵得到对应的 f 值进行修改即可。

查询就是根结点所在重链的转移矩阵乘积。

12.9 P4381 [IOI 2008] Island

基环树森林直径之和。可分为直径不经过环和经过环两种情况。第一种情况直接按在树上求直径的方式求即可。第二种就断环为链，设 s_i 为边权的前缀和，d_i 为点 i 子树到点 i 最长路径。则对于从点 u 进入 v 出去的环，边权和即为 d_u+d_v+s_v-s_u，考虑枚举 u，则相当于在长度为 len-1（len 为环长）的区间找 d_v+s_v 的最大值，使用单调队列。

12.10 P2607 [ZJOI2008] 骑士

基环树最大权独立集。断开一条环上的边，分别对边两端点 dp，且钦定两点一个选一个不选。

12.12 P5049 [NOIP 2018 提高组] 旅行 加强版

基环树字典序最小 dfs 序（可提前回溯），显然一条边最多走两次。先将每个点连向的点排序。先走到环，之后我们有向左右走两种选择，选择编号较小的那方走到再走这边是不优的，然后回溯到另一边走完环后回溯到环的进入点并把到根的剩下的点 dfs 了。并且边走环边把当前点的儿子中编号小于下一个环上点的儿子的子树都 dfs 了，之后回溯的时候把剩下的子树 dfs 了。

“再走这边是不优的”就意味着从这个点回溯第一个走到的点比下一个环上点小，这个很好处理。

12.13 CF613D Kingdom and its Cities

建虚树然后 dp。先把无解判了：如果有一条边连接两个关键点就无解。设 f_i 表示考虑点 i 的子树的答案，g_i 表示在点 i 的子树中有没有关键点与点 i 联通（关键点的本身与自己联通）。首先有 f_u=\sum_{v\in son_u} f_v。然后：如果点 u 是关键点，就需要将子树中所有与之联通的关键点断开，即 f_u \leftarrow f_u+\sum_{v\in son_u} g_v。如果点 u 不是关键点，且其子树中有大于 1 个关键点与之联通，则将自己断开；如果只有 1 个，则令 f_u=1，也就是在此处可能不需要断开自己，因此传递到父亲处考虑。

12.14 P2491 [SDOI2011] 消防

树上距离一个点最远的点一定是直径端点。考虑一个不在直径上的点，在它靠近直径的过程中与直径端点的距离一定减小，故答案路径与直径必定有交。如果在一段直径上接一段不在直径上的路径组成答案，你会发现后者对答案是没有贡献的，因为它们不会改变最远距离（最远距离一定是那段直径的端点到直径端点的距离），故答案一定可以全部在直径上。

一段直径上的路径的最远距离由 3 部分组成：

• 路径左端距离直径左端的距离。

• 路径右端距离直径右端的距离。

• 路径上每个点的不包含直径的子树中距离其的最远距离。

对于最后一条，每个点用 dfs 预处理出。我们枚举左端点，前两条就是好处理的。最后一条需要求的就变成了区间的一段中的最大值，用单调队列。

12.16 P5666 [CSP-S 2019] 树的重心

考虑点 u 什么时候会成为重心：把 u 作为树根，删除大小大于整体一半的子树使其大小不大于一半，设 sz_u 为点 u 的子树大小，h_u 为点 u 的重儿子，删除的子树大小为 s，则 n-s-sz_u\le \frac{n-s}{2} 且 h_u\le\frac{n-s}{2}，变形可得：n-2sz_u\le s \le n-2h_u。以重心为根，这样要删除的边一定不在 u 子树内。

我们需要单独考虑根的答案，设根的重儿子为 x，次重儿子为 y，则如果删除的边在 x 子树中，需满足：s_y\le\frac{n-s}{2}，即：s\le n-2s_y；否则需满足：s_x\le\frac{n-s}{2}，即 s\le n-2s_x。

先不考虑边不在子树内的限制，我们可以将所有的 sz_i 存到树状数组里，动态维护以每个点作为根时所有点的 sz（将树状数组作为桶）：每次将遍历的点 x 的父亲 fa 的子树大小 sz_{fa} 改为 n-sz_x。然后两次单点查询。

然后我们就需要去除在 u 子树的贡献。再开一个树状数组在 dfs 时动态加入 sz，这时需要去除的就是遍历完子树后 减去 刚遍历时的对应范围的值。

12.19 P8966 觅光 | Searching for Hope (easy ver.)

题解

12.19 P8968 觅光 | Searching for Hope (hard ver.)

题解

12.21 P9013 [USACO23JAN] Find and Replace S

考虑将 s_i \rightarrow t_i 作为边建出图。显然颜色一样的位置永远都一样，故如果有出度的大于 1 的点就无解。否则所有点出度都小于等于 1，这个形态有三种可能：

• 树：按照自顶向下的顺序依次将某个节点修改为他连向的节点，需要边数次操作。

• 内向基环树：考虑每个环上的点 u，如果一个树 T 和另一个环上的点 v 都连向它，则树 T 内 u 的子节点和 v 都需要修改为 u。可以先将树 T 内 u 的子节点都修改为 v，然后处理剩下的树的部分，最后将所有 v 修改为 u，需要边数次操作。例子 s=\texttt{ABCD},t=\texttt{BCBC}，需要 4 次。

• 环：需要断开环：将某一个点修改为一个没有出现过的字母，然后就是一个链（树）了，需要边数加 1 次操作，故如果 t 中 52 种字母都有就不行。

综上，答案为总边数加纯环的数量。

12.21 P5597 【XR-4】复读

因为第一遍执行后到达的点必定比根深度大，故执行完任意一轮后，如果到了点 u，需要满足 u 之外的点都遍历了。考虑枚举这个点 u，将每一轮执行需要经过的点合并成一棵树，然后此时的答案即为树的边数的两倍减去 u 到根的长度。

12.22 CF1076E Vasya and a Tree

考虑离线，将询问挂到点上。然后 dfs，开一个树状数组，遍历到一个点就就将此处每个询问影响的最深深度在树状数组上加上对应的 x，每个点的答案就是从点深度开始的后缀和。

12.28 P14829 [THUPC 2026 初赛] Asian Soul

考虑离线，将询问存到线段树对应节点上，然后把每个线段树节点看作询问计算答案。设当前节点的范围为 [l,r]。每个存在这个节点的询问的答案是它到根的路径上所有满足除了与这条路径相交的子树外，其余子树中还有编号在 \{a_i | i \in \{a_l,a_{l+1},\dots ,a_r\}\} 的点的点的编号的最大值，这个可以通过 dfs 预处理每个节点子树内编号在如上范围内的点的数量，然后再 dfs 计算答案实现。还需要建虚树，考虑用归并排序和单调栈建虚树的方法 O(n) 建虚树。

统计

共写：123 题。