2026年2月专项训练巩固总结

图的连通性问题

遇到最多的是强连通分量以及割边（桥）的判定，其他的目前遇到的还比较少。

设 dfn[u] 表示 DFS 到 u 的时间戳，但 low 数组有一些不同：

• SCC的 low：能走到的还在栈中的最小的 DFS 序号。
• 割边的 low：不经过父边，能够走到的最小的 DFS 序号。如果 low[v] > dfn[u]，说明 v 回不到 u 以及更祖先的点，说明 (u, v) 是桥。

强连通分量

这是有向图里的概念。

割边（桥）

割边是无向图里的概念。

割边有一条重要的性质，即割边一定出现在这个图的生成树/生成森林里面，根据生成树里的父子关系，可以通过预处理树的信息，维护删掉割边之后，两个连通分量各自的信息，即一个是子树的信息，一个是总的减去子树的。

重链剖分

对于一棵树来说，考虑其结点 $u$，其儿子中子树最大的那个，叫做重儿子，不妨记为 $son[u]$。其他儿子叫做轻儿子。

我们把 $u$ 和 $son[u]$ 之间的边叫做重边，$u$ 和轻儿子之间的边叫做轻边。

由于轻儿子的大小小于等于重儿子的大小，所以假如某个 $v$ 是 $u$ 的轻儿子，则 $sz[u] > 2 \times sz[v]$。假如我们的树一共有 $n$ 个结点，则对于一个结点来说，其到根的路径上，至多遇到 $O(\log n)$ 条轻边。

引入 DFS 序的话，如果优先遍历重边，则重链的 DFS 序是连续的。

使用重链剖分后，树上的一条路径可以被分成 $O(\log n)$ 条链，每条链上 DFS 序连续，可以用维护区间的数据结构去维护。

树上启发式合并

只要是子树相关的统计问题，且不要求强制在线，都可以试试树上启发式合并。

假如某个题，需要我们暴力遍历每个 $u$ 子树去计算一个东西，那么复杂度就至少是 $O(n^2)$。

考虑如何优化这个复杂度，我们可能会想，假如我们要暴力算 $u$ 子树里的东西，因为我们还要算 $u$ 的孩子 $v$ 子树里的东西，假如 $v$ 子树里算好的能保留下来，我们是不是能少遍历一些？

其实是可以的。我们能想到，如果在想算 $u$ 子树的答案时，能不重复遍历 $u$ 的重儿子 $v$ 子树里的结果，应该是上面这个思路能做到的最好的情况。而轻儿子，我们还是暴力去搞了。

这样我们其实就是做下面几个步骤：

1. 我们想算 $u$ 子树的结果。
2. 先暴力递归算 $u$ 的轻儿子 $v$ 的子树里的结果，但不保存计算时维护的数据（dfs(v, u, false)）。
3. 再暴力递归算 $son[u]$ 里的结果，但算好之后从 $son[u]$ 中退出时，保留计算过程中维护的数据（dfs(son[u], u, true)）。
4. 最后，对于 $u$ 子树来说，其现在有现成的已经算好的 $son[u]$ 的数据，我们只需要把 $u$ 的单点加进去（add_node(u, 1)），再暴力把所有轻儿子遍历一遍（add_subtree(v, u, 1)），就好了。
5. 最最后，假如 $u$ 子树计算中维护的数据不需要保存的话（即 $u$ 自己是 $fa$ 的轻儿子），需要清空（add_subtree(u, fa, -1)）。

上面描述的这个过程的复杂度是多少呢？我们其实只需要考虑某个结点 $u$ 到底被暴力遍历了多少次。

可以注意到，每当遇到 $u$ 到根的路径上的一条轻边时，就说明 $u$ 又在某个轻儿子的子树里，说明它又要被遍历一遍。

基于重链剖分部分的理论，我们可以知道，每个点头顶上的轻边至多有 $O(\log n)$ 条，所以每个点至多被重复统计 $O(\log n)$ 次，所以把所有点为根的子树的结果都算好，其实只需要 $O(n\log n)$ 的时间（如果维护每个点每次被遍历到的信息的时间是 $O(1)$，当然你也可能是维护了一个全局的复杂数据结构，这样单次操作可能就是 $O(\log n)$）。

因为我们是按照 DFS 的顺序算的每个子树的答案，所以树上启发式合并一般来说是“离线”的。

能用树上启发式合并做的题，一般可能也有别的做法，比如莫队，比如值域线段树合并之类的，这些是后话了，我还不太会。

扫描线、离线二维数点

扫描线实际上是个内涵很广的概念，最近几天的训练中，我至少遇到了下面几种：

• 矩形面积并类型的，需要拆成左边和右边，遇到左边时加入影响，遇到右边时移除影响。
• 二维数点里面，我们想求某个矩形里点的个数，考虑矩形拆成左右两个边，所有边和点按照横坐标排序，从左往右扫，遇到左边时，往这个询问里减掉当前的前缀和，遇到右边时，加上当前的前缀和。
• 事实上，单点可以看成是 1x1 的矩形，所以对单点进行计数其实是矩形面积并的一个特例！

离线二维数点问题其实是很重要的一个问题，很多问题能转化为此类问题，所以一定要多回顾多思考！

最近做的最复杂的一道二维数点题目：P11625，其可以转化为，有一堆平行于 x 轴的线段，每次给一个矩形，询问矩形内部的线段的长度（不必完全覆盖一整条线段，覆盖一部分就算这部分的长度）。这个事情如果按照 x 离线会很难做，因为线段垂直于 y 轴，我们要维护某个 y 坐标上累计被覆盖了多久，这个很难搞。如果按照 y 离线，则线段只需要用 x 轴上的线段树区间加就好了，询问时就是求 x 轴上的对应区间的区间和。这说明了按照哪个坐标离线，做法的难度可能很不一样。

代码上的一些记录：TBD。

DP加速矩阵构造

之前只会类似于 $dp[i] = dp[i - 1] + dp[i - 2]$ 这种类型的矩阵构造，最近遇到了一个不太一样的方程：

$dp[i] = dp[i - 1] \times 10^t + i$。

我们可以注意到，$dp[i]$ 和 $dp[i - 1]$ 和 $i$ 有关系，，所以我们容易想到答案向量至少得是 $[dp[i],i + 1]$ 这样的东西，但 $[dp[i - 1], i]$ 虽然能转移出来 $dp[i]$，但转移不出来 $i + 1$，还差一个 $1$，所以答案向量应该设成 $[dp[i], i + 1, 1]$，这样就可以构造出转移矩阵：

$\begin{bmatrix} 10^t & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix}$

所以转移就是：

$\begin{bmatrix} dp[i]\\ i + 1\\ 1 \end{bmatrix} = \begin{bmatrix} 10^t & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} dp[i - 1]\\ i\\ 1 \end{bmatrix}$

数位DP

首先讲一下模板：dfs(u, info, is_limit, is_num)：

• u 是当前的位下标
• info 是我们需要维护的已经填的前缀的信息，比如填的数之和是多少，某个数码用了多少次，上一个数码是谁之类的。
• is_limit 为 true 时，代表我们已经填的前缀和上界是相等的，所以我们目前能填的数最大到 s[u]；如果是 false，说明这一位最大可以填 9。
• is_num 为 true 时，代表前面已经填过数了，所以这一位可以最小从 0 开始填；false 说明前面还没填过数，这一位最小得从 1 开始填。

我们考虑何种状态是可以复用计算结果的，显然得是那些从 0 到 9 都能填的，也就是 is_limit = false 且 is_num = true，这样的状态都是可以记忆化和复用的，所以我们本质上是记忆化的 dp[u][info][false][true]，但因为后两维固定了，所以只需要用 dp[u][info] 两维就够了。

代码模板贴一下，这个需要时常回顾，常看常新：

/*
计算 [0, 10^n) 中有多少无重复数码的数
*/
class Solution {
public:
    string s;
    int dp[10][1024];

    int calc(int i, int mask, bool is_limit, bool is_num) {
        if (i == s.size()) {
            /*
            能运行到这儿，说明无重复数码，且在范围内
            有些题要求 [1, n] 之间的数，这个时候如果 is_num = false，则说明没填数
            没填数等价于填的就是 0，且这是唯一能表达我们填了 0 的方式
            本题是 [0, n] 之间的数，所以 0 也是合法的，返回 1 即可
            如果是 [1, n] 之间的数，则 0 是非法的，我们可以返回 is_num ? 1 : 0
            */
            return 1;
        }
		
        // 能随便填 0-9 时，才是我们 dp 定义的状态，才能用算好的结果
        if (!is_limit && is_num && dp[i][mask] >= 0) {
            return dp[i][mask];
        }

        int res = 0;
        // 先判断一下之前是否填过数，没填过的话先把这一位也不填的情况算了
        if (!is_num) {
            res = calc(i + 1, mask, false, false);
        }
        // 根据 is_limit 和 is_num 计算枚举的上下限
        int up = is_limit ? (s[i] - '0') : 9;
        int down = is_num ? 0 : 1;
        for (int d = down; d <= up; d++) {
            if (((mask >> d) & 1) == 0) {
                // 注意递归下去的 is_limit 和 is_num 的值
                res += calc(i + 1, mask | (1 << d), is_limit && d == up, true);
            }
        }
        // 能随便填时，需要把算好的结果存到 dp 中
        if (!is_limit && is_num) {
            dp[i][mask] = res;
        }
        return res;
    }

    int countNumbersWithUniqueDigits(int n) {
        int t = 1;
        for (int i = 1; i <= n; i++) {
            t *= 10;
        }
        s = to_string(t - 1);
        memset(dp, -1, sizeof dp);
        return calc(0, 0, true, false);
    }
};

事实上这个模板是可以变的，有时候我们可能会遇到要同时维护两个有上界的数的情况，这个时候每个数可能都要维护 is_limit。

数位 DP 的思想也很常用，即枚举前 $i$ 位一样，从第 $i + 1$ 位开始严格小，后边就可以随便填了，这个思路可以帮助我们做很多题。

欧拉定理/降幂

我们可能会遇到计算 $a^b$ 对 $m$ 取模，但 $b$ 也是一个需要计算的很大的数的情况，其大到是个高精度数。

直接对 $b$ 取模 $m$ 是错误的，那么怎样降幂才是正确的呢？

如果 $m$ 是素数，我们其实知道 $a^{m - 1}\equiv1(mod\ m)$ ，这是费马小定理。所以这种时候，可以计算 $b$ 时对 $m - 1$ 取模，即可把幂次降下来。

对于更一般的情况，需要使用欧拉定理去降幂。

贪心