Frosti

集训汇总

Fri Jul 25 2025
9 minutes
算法学习笔记 OI 数据结构 图论 数学 DP DP 优化
1659 words

学到了 + 恶补了一车东西，写这里。

树相关#

本质都是对某个节点按某种规则分出重儿子

重链剖分 & DSU On Tree#

重链剖分#

性质是任意一条路径上只有 O(log⁡n)\Omicron(\log n) 条轻边，也就是说只和 O(log⁡n)\Omicron(\log n) 条重链相关。

本质上是一种链分治，所以对于某些问题可以分重儿子和轻儿子分类讨论后合并信息。

DSU On Tree（树上启发式合并）#

每个节点的轻子树的大小和是 O(nlog⁡n)\Omicron(n \log n) 的，所以对于某些和子树大小相关的问题，可以考虑继承重儿子的信息后加上自己的，随后合并轻儿子。

实现上可以考虑开一个内存池，然后 DP 数组保存指针。

小的往大的和，启发式没错了（

两个合称静态链分治。

动态 DP#

下文中 son(u)\text{son}(u) 表示 uu 的所有儿子，LSon(u)\text{LSon}(u) 表示 uu 的所有轻儿子,HSon(u)\text{HSon}(u) 表示 uu 的重儿子。

来解决一些会修改点权的简单树上问题，下面拿动态点权树上最大独立集为例。

首先朴素 DP 长这样子：{dpu,0←∑v∈son(u)max⁡{dpv,0,dpv,1}dpu,1←au+∑v∈son(u)dpv,0\begin{cases} dp _ {u,0} \gets \sum \limits _ {v \in \text{son}(u)}\max \{dp _ {v,0},dp _ {v,1}\} \\ dp _ {u,1} \gets a _ u + \sum \limits _ {v \in \text{son}(u)} dp _ {v,0}\end{cases}

如果我们修改点权暴力做，显然需要更新那个点所有祖先的 dpdp 值，最劣单次 O(n)\Omicron(n)。

我们想，既然是对链操作，那我们为什么不能拿树剖来做呢？但是树剖只能剖出链，维护还得用其他方式，所以我们考虑数据结构维护。

首先一般数据结构维护的是半群信息，得有结合律，所以我们用矩阵维护 dpdp 数组，使其具有结合律，然后用线段树维护。

但是一个点不只有重儿子，所以我们定义 gu,0/1g _ {u,0/1} 表示不选/选 uu 的轻儿子信息并，则 {gu,0←∑v∈LSon(u)max⁡{dpv,0,dpv,1}gu,1←au+∑v∈LSon(u)dpv,0\begin{cases} g _ {u,0} \gets \sum \limits _ {v \in \text{LSon}(u)} \max\{dp _ {v,0},dp _ {v,1}\} \\ g _ {u,1} \gets a _ u + \sum \limits _ {v \in \text{LSon(u)}} dp _ {v,0} \end{cases}

所以修改后，有 {dpu,0=max⁡{dpHSon(u),0,dpHSon(u),1}+gu,0dpu,1=dpHSon(u),0+gu,1\begin{cases} dp _ {u,0} = \max \{dp _ {\text{HSon(u),0}},dp _ {\text{HSon}(u),1} \} + g _ {u,0} \\ dp _ {u,1} = dp _ {\text{HSon(u),0}} + g _{u,1} \end{cases}

然后放到矩阵上来，max⁡\max 对 ++ 有分配律，所以 (max⁡,+)(\max,+) 矩阵乘法是有结合律的。

我们的 DP 顺序是由深到浅，对应 DFN 是由大到小，所以 dpdp 的矩阵应该放在右边，所以矩阵为 [dpu,0dpu,1]\begin{bmatrix} dp _ {u,0} \\ dp _ {u,1} \end{bmatrix}，自行推导出转移矩阵为 [gu,0gu,0gu,1−∞]\begin{bmatrix} g _ {u,0} & g _ {u,0} \\ g _ {u,1} & -\infty \end{bmatrix}。

考虑修改，我们修改一个点的点权，只会影响到它到根路径上的所有轻边，轻边数量由重剖的性质可得是 O(log⁡n)\Omicron(\log n) 的，带上线段树的复杂度单次是 O(log⁡2n)\Omicron(\log ^ 2 n) 的。

还有一种直接对重链建二叉树的全局平衡二叉树写法，但我不会。

实现
CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/extc++.h>
using namespace std;
#define int long long 

constexpr int MAXN = 1e5 + 5,inf = 0x3f3f3f3f3f3f3f3f;
int n,m,a[MAXN];
vector<int> g[MAXN];
struct Matrix
{
    int val[3][3];
    Matrix()
    {memset(val,~0x3f,sizeof(val));}
    Matrix operator*(Matrix rhs) 
    {
        Matrix res;
        for(int i = 1;i <= 2;i++)
        {
            for(int k = 1;k <= 2;k++)
            {
                for(int j = 1;j <= 2;j++)
                    res.val[i][j] = max(res.val[i][j],val[i][k] + rhs.val[k][j]);
            }
        }
        return res;
    }
}tree[MAXN << 2],val[MAXN];
int f[MAXN],dep[MAXN],sz[MAXN],top[MAXN],son[MAXN],dfn[MAXN],id[MAXN],timer,dp[MAXN][2],ed[MAXN];
inline void dfs1(int u,int fa)
{
    f[u] = fa,dep[u] = dep[fa] + 1,sz[u] = 1;
    for(int v : g[u])
    {
        if(v == fa)
            continue;
        dfs1(v,u);
        // 计算 dp 的值
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v])
            son[u] = v;
    }
}
inline void dfs2(int u,int tp)
{
    dfn[u] = ++timer,id[timer] = u;
    top[u] = tp,ed[tp] = timer;
    // 给 g 赋初始值，直接存进矩阵
    if(!son[u])
        return ;
    dfs2(son[u],tp);
    for(int v : g[u])
    {
        if(v == f[u] || v == son[u])
            continue;
        dfs2(v,v);
        // 计算 g 的值
    }
}
inline void pushup(int rt)
{tree[rt] = tree[rt << 1] * tree[rt << 1 | 1];}
inline void build(int rt,int l,int r)
{
    if(l == r)
    {
        tree[rt] = val[id[l]];
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt << 1,l,mid),build(rt << 1 | 1,mid + 1,r);
    pushup(rt);
}
inline void modify(int rt,int l,int r,int pos)
{
    if(l == r)
    {
        tree[rt] = val[id[l]];
        return ;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        modify(rt << 1,l,mid,pos);
    else
        modify(rt << 1 | 1,mid + 1,r,pos);
    pushup(rt);
}
inline Matrix query(int rt,int l,int r,int L,int R)
{
    if(L <= l && R >= r)
        return tree[rt];
    int mid = (l + r) >> 1;
    if(R <= mid)
        return query(rt << 1,l,mid,L,R);
    if(L > mid)
        return query(rt << 1 | 1,mid + 1,r,L,R);
    return query(rt << 1,l,mid,L,R) * query(rt << 1 | 1,mid + 1,r,L,R);
}
inline void Pmodify(int u,int w)
{
    // 更新那个点的信息，先改 val 矩阵
    Matrix pre,cur;
    while(u)
    {
        pre = query(1,1,n,dfn[top[u]],ed[top[u]]); // 这条链改之前的矩阵
        modify(1,1,n,dfn[u]); // 线段树上同步
        cur = query(1,1,n,dfn[top[u]],ed[top[u]]); // 改之后的
        u = f[top[u]];
        // 把之前的减掉再加上新的来更新链顶的点的矩阵
    }
}

长链剖分#

重儿子是到叶子节点的路径最长的儿子，性质是任意一条边上有 O(n)\Omicron(\sqrt{n}) 条轻边。

应用没有重剖多，有两个应用：求 kk 级祖先和优化 DP。

求 kk 级祖先没什么用，跑不过重剖，主要应用是优化 DP。

上面 DSU On Tree 是来优化和子树大小有关的问题，而长剖是用来优化和深度有关的问题的。

Eg. CF1009F Dominant Indices#

我们考虑在 uu 子树中与 uu 的距离为 dd 的怎么算，考虑 DP，则 dpu,d=∑v∈Son(u)dpv,d−1dp _ {u,d} = \sum _ {v \in \text{Son}(u)} dp _ {v,d - 1}，显然会炸。

考虑优化，这个和深度有关，考虑长剖。先给 dpu,0dp _ {u,0} 设为 11，然后把重儿子的 dpdp 指向 dpudp _ u 的下一个再进行递归，这样就可以直接继承重儿子了，轻儿子暴力做就行。

然后答案先设为长链长度，然后合并轻儿子时更新。

DP 相关#

动态 DP#

写上面了。

DP 套 DP#

某些最优化/可行性 DP 可以被看作是一个 DFA，所以 DP 套 DP 的实质是 DFA 上的 DP，所以你可以以理解 ACAM DP 的方式来理解这个东西。

内层 DP 的结果就是 DFA 的状态，所以外层 DP 的状态会与内层 DP 的结果有关。

考虑外层 DP 的时候，我们要能把内层 DP 整个表示出来，所以可能需要记一些和内层 DP 转移相关的东西。

然后一般不会直接让你过的，所以你可能需要观察一些性质。

Updating…