c_wInf's blog
0%

如何有技巧地爬树

Posted on Edited on

树上dp

什么是树上dp？字面意思，在树上做dp

但是这个描述不准确，更准确应该是树形dp，树上dp可能只是在树上，有一个dp，不一定是树状转移状态的

状态转移的方向：自顶向下/自底向上

自顶向下需要为根节点设计初始状态，自底向上需要为所有叶子节点设计初始状态，这里可能是不同的

一个自顶向下的例子：树上差分/前缀和

自顶向下时一个结点的多个子结点会共用一个dp状态栈，所以需要利用回溯的性质

自底向上时一个结点会从多个子结点来转移状态，所以状态转移方程会更复杂；且子结点树可能是\(O(n)\)的，对于关于子结点数\(k\)时间复杂度\(\Omega(k^{1+\epsilon})\)的转移计算方法，菊花树会爆，此时要考虑在子结点上做一些操作比如排序/在子结点上维护数据结构/启发式合并状态/设计逐结点转移方程/拆点拆边

树形dp

例题：没有上司的舞会

题解

一个结点出不出席影响子结点的出席情况，所以设计状态时要分类讨论

f[x]代表考虑结点x子树来参加舞会且x本身出席的最大快乐指数，g[x]代表考虑结点x子树来参加舞会且x本身不出席的最大快乐指数，那么我们可以得到转移方程

\[ f[x] = r[x] + \sum_{y:x} g[y] \]

\[ g[x] = \sum_{y:x} \max (f[y], g[y]) \]

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef int64_t lint;
std::vector<int> adj[maxn];
lint r[maxn];
int n;

std::pair<lint, lint> dfs (int x, int fa) {
    lint f = r[x], g = 0;

    for (int y : adj[x]) {
        if (y != fa) {
            auto [sf, sg] = dfs (y, x);
            f += sg, g += std::max (sf, sg);
        }
    }

    return {f, g};
}

lint solve () {
    auto [f, g] = dfs (1, 1);
    return std::max (f, g);
}

树上背包

在树上做背包，比传统背包多了合并背包的操作，实质是一个卷积

树上背包通常时间复杂度是\(O(nm)\)，其中\(n\)是结点数，\(m\)是选点数(背包状态数)，具体见例题

例题：树上染色

题解

选黑色结点其实就是背包，k就是背包容量，只能装进k个结点，最后最大化价值，所以状态会有两维

设计状态的时候，我们发现如果f[i][j]代表给结点i的子树染色，其中j个结点为黑色，能够获得多少收益，那么很难计算跨子树部分的收益，所以改为统计能够有多少贡献

考虑具体对贡献值的定义时，我们发现距离的贡献可以被拆解到树边的贡献，所以只需要统计子树内所有边有多少贡献就可以了

那么在状态转移时，除了合并子树贡献，还有一些连接根和儿子的边的贡献没被计算，这些边贡献和边下染了几个黑结点有关

最后类似树上背包依次把每个儿子的贡献并进去就可以了

我们写出转移方程：

\[ f[x][j] = \max_{i=0}^{j} (f[x][j-i] + f[y][i] + w[y] (i(k-i) + (s[y]-i)(n-k-s[y]+i))) \]

其中x是当前枚举的结点，y是当前枚举的子结点，s[y]是y的子树大小，w[y]是x和y所连边的边权

我们发现每次合并背包的时候要做一次大小至多为\(k\)的卷积，导致总时间复杂度会是\(O(nk^2)\)，但是假如每次背包的时候我们对i进行上下界剪枝：

\[ \max(j - S, 0) \le i \le \min(j, s[y]) \]

这里S是已经枚举过的所有子结点的子树大小之和(不包括当前枚举子结点y)，那么我们发现每次计算转移方程时间\(O(s[y]S)\)，累加得到\(O((\sum_{y:x}s[y])^2 - \sum_{y:x}s[y]^2)\)，这个复杂度沿树累加，会得到\(O((\sum_{y:r}s[y])^2) = O(n^2)\)，发现成功从立方优化到了平方

对这个神奇的优化还有一种理解方式，就是背包合并的复杂度可以视为不同子树结点两两合并，而每两个结点只会在lca处合并一次，所以就是\(O(n^2)\)了

实际上的复杂度是\(O(nk)\)，因为\(k\)限制了最大背包状态数，具体证明略过

参考代码：

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
typedef int64_t lint;
std::vector<std::pair<int, lint>> adj[maxn];
lint f[maxn][maxn];
int s[maxn];
int n, k;

void dfs (int x, int fa) {
    s[x] = 1;

    for (auto [y, w] : adj[x]) {
        if (y != fa) {
            dfs (y, x);
            s[x] += s[y];

            for (int j = std::min (k, s[x]); j >= 0; --j) {
                int mini = std::max (j - s[x] + s[y] + 1, 0);
                int maxi = std::min (j, s[y]);

                for (int i = mini; i <= maxi; ++i) {
                    lint nedge = (i*(k-i) + (s[y]-i)*(n-k-s[y]+i));
                    lint fc = f[x][j-i] + f[y][i] + w * nedge;

                    if (dp[x][j] < fc) dp[x][j] = fc;
                }
            }
        }
    }
}

lint solve () {
    k = std::min (k, n - k);
    dfs (1, 1);
    return f[1][k];
}

换根

换根就是指定一个任意结点，当成根节点，看对这棵树和一些别的状态有什么影响

例题：STA-Station

题解

对一个结点计算深度之和复杂度是\(O(n)\)，但是对每个结点都算一遍就\(O(n^2)\)炸了，所以考虑换根

简单来说，假设以x为根节点的深度和已经算完了，我们需要考虑把根节点换到x的子结点y时深度和怎么变

我们发现，y子树内的结点深度都会-1，子树外的结点深度都会+1，所以可以写出状态转移方程

\[ f[y] = f[x] - s[y] + (n - s[y]) \]

其中\(s[y]\)是y子树的大小

参考代码：

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
typedef int64_t lint;
std::vector<int> adj[maxn];
int s[maxn], d[maxn];
int n;
lint f[maxn];

void dfs1 (int x, int fa) {
    s[x] = 1;
    for (int y : adj[x]) {
        if (y != fa) {
            d[y] = d[x] + 1;
            dfs1 (y, x);
            s[x] += s[y];
        }
    }
}

void dfs2 (int x, int fa) {
    for (int y : adj[x]) {
        if (y != fa) {
            f[y] = f[x] + n - s[y]*2;
            dfs2 (y, x);
        }
    }
}

int solve () {
    d[1] = 0;
    dfs1 (1, 1);

    f[1] = 0;
    for (int i = 1; i <= n; ++i) f[1] += d[i];

    dfs2 (1, 1);

    int ans = 1;
    for (int i = 2; i < n; ++i) {
        if (f[i] > f[ans]) ans = i;
    }
    return ans;
}

重心

讲重心之前先补充一些前置芝士

一棵有根树中，结点的重量是指以该结点为根的子树的结点数量；对于一个结点的各个儿子结点，我们把重量最大的儿子称为重儿子，其它的称为轻儿子。

区分轻重儿子有什么用呢？我们可以证明，对于一棵大小为\(n\)的树，任何一个结点到根的路径上最多只有\(\log n\)条轻边，剩下全是重边

这个性质就可以让我们进行启发式合并，每个结点在轻边上会被暴力一次，所以暴力总次数被控制到\(O(n\log n)\)

反过来想，每个节点到根节点的路径上只有少量的轻边，意味着路径可以分为至多\(\log n\)段，每一段上都是重边

于是我们自然地会有重链的概念：从一个结点开始，一直找重儿子直到叶子结点所产生的路径

具体来看道题

例题：软件包管理器

题解

在优先遍历重儿子的dfs序上考虑这个问题，我们发现卸载操作转化成了对区间的卸载，安装操作转化成了对至多\(\log n\)段区间的安装，所以只要配合线段树/珂朵莉树维护软件状态就好了，虽然双\(\log\)但是随机数据常数很低，这是因为大部分结点都跑不满\(\log n\)条轻边

时间复杂度\(O(n\log^2 n)\)

参考代码：

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
void assign (int l, int r, int v);
int count (int v);

std::vector<int> adj[maxn];
int w[maxn], wson[maxn], fat[maxn];
int ndfs[maxn], npdfs[maxn], wanc[maxn];

void dfs1 (int x, int fa) {
    w[x] = 1;
    wson[x] = 0;
    fat[x] = fa;
    for (int y : adj[x]) {
        if (y != fa) {
            dfs1 (y, x);
            w[x] += w[y];
            if (wson[x] == 0 || w[wson[x]] < w[y])
                wson[x] = y;
        }
    }
}
void dfs2 (int x, int fa) {
    static int dfsk = 0;
    ndfs[x] = dfsk++;

    if (wson[x]) {
        wanc[wson[x]] = wanc[x];
        dfs2 (wson[x], x);

        for (int y : adj[x]) {
            if (y != fa && y != wson[x]) {
                wanc[y] = y;
                dfs2 (y, x);
            }
        }
    }

    npdfs[x] = dfsk;
}

void install (int x) {
    while (true) {
        assign (ndfs[wanc[x]], ndfs[x] + 1, 1);
        if (x == 1) break;
        x = fat[wanc[x]];
    }
}

void uninstall (int x) {
    assign (ndfs[x], npdfs[x], 0);
}

void init () {
    dfs1 (1, 1);
    wanc[1] = 1;
    dfs2 (1, 1);
}

对于一棵树，如果拿走一个结点后，剩下的子碎树片大小都不超过原树大小的一半，就把这个结点称为重心

重心有很多很多很多很好的性质，所以我们可以出很多很多很多关于重心的好题

  1. 每棵树都有1或2个重心；如果有两个重心，那么这两个重心必定相邻
  2. 重心是到所有结点距离之和最小的点
  3. 在树上增/删一个叶子结点，重心至多只移动一条边的距离
  4. 一颗有根树的重心一定在根的重链上
  5. 一颗有根树的重心一定是重子树的重心的祖先
  6. 一颗有根树的重心一定是dfs序中位数结点的祖先
  7. 把两棵树相连得到一颗新树，那么新树的重心一定在原两树重心的最短路径上

证明可以看看这个

那么，怎么求重心呢？利用一下上面的性质，先dfs一遍求重量，再从根往下找重儿子检查哪个是重心就可以了

那么，如果要动态维护重心呢？需要根据具体动态操作决定，可以考虑点分治/lct/拆点拆边/各种离线大法不讲不讲

例题：树的重心

因为重心有很多妙妙性质，所以这道题有无数种做法

题解1

无论什么做法基本都要预处理每个结点重量和重儿子编号来快速判断一个结点是不是重心

我们枚举要剪掉的边

利用重心位于dfs序中点祖先上的性质，因为一棵子树在dfs序上是连续的，我们可以方便地求出剪边后两部分的dfs序中点，然后树上倍增二分求重心即可，这里要判断有没有扣掉检查结点的一些子孙结点所以需要lca，注意双重心情况

时间复杂度\(O(n\log n)\)

题解2

同样枚举要剪掉的边

对边下面的子树考虑重心在重链上的单调性，在重链上双指针就可以了，注意双重心情况

对边外面的部分，我们以整棵树的重心为根，剪边时重心从根向重儿子移动(如果要剪掉的边在根的重子树上则向次重儿子移动，如果有不止一个次重儿子那么不会移动)，分类讨论剪边在不在重子树上然后按减去重量-重心位置打个表就可以了，任何线性复杂度算法都可以

时间复杂度\(O(n)\)

题解3

是一个题解2在线的做法，我们可以以任意结点为根快速求出删任意一条边得到的重心，代价是复杂度多一个\(\log\)

对边下面的子树我们直接在重链上二分，注意双重心情况

对边外面的部分考虑换根转化为第一种情况，我们发现换根后重链一定是一条爬若干次(可能为0)父亲然后沿原树重链到底的一条链，所以只要先倍增向上跳，找到重心在哪个祖先子树上，再沿重链往下二分就可以了

需要预处理一下重链和倍增那你在线了个寂寞

时间复杂度\(O(n\log n)\)

题解4

我们求每个结点对答案的贡献，也就是能做多少次重心

首先还是找到整棵树重心作为根，先算根节点贡献，做预处理的时候直接判就可以了，注意分类讨论剪边是否在重子树上

对于别的结点x，假设我们要剪掉以y为根的子树

我们注意到剪掉一颗子树重心只会远离它往外跑，所以剪掉的边肯定不在x的子树里面

我们设s[]代表子树重量，t[]代表重子树重量(如果是叶子结点没有儿子那么为0)，那么可以列出满足x为重心的方程

\[ \begin{cases} 2 (n - s[x] - s[y]) \le n - s[y] \\ 2 t[x] \le n - s[y] \end{cases} \]

化简得到一个只和x有关的、对y的约束

\[ n - 2s[x] \le s[y] \le n - 2t[x] \]

对每个x，我们要统计满足y在x子树外面(允许y=x)且满足上述约束的y的数量

如果只有不等式约束条件，我们只要统计每一个s[y]值有多少个，然后做区间求和就可以了

但是我们要剔除一个去掉根结点的子树再统计，那么考虑到剔除的结点在dfs序上是连续的区间，那么我们只要离线询问+动态统计一段值域上频率就可以了，值域树状数组就行，当然你也可以用主席树来在线

时间复杂度\(O(n\log n)\)

淀粉质

机考不会出现的神秘算法，模板即是蓝题

点分治，就是按照点在一颗树上分治那么同样有边分治只不过也能用点分治来写

一般的分治要在区间上找到中点，然后分治左右子区间，最后合并结果，那么点分治就是在树上找到重心，然后切成若干小的子树，最后合并结果

通过点分治可以规避树链过长问题，最多分治\(O(\log n)\)次就可以到达任意结点；同时，点分治在无根树上也能做，所以适合处理一些根无关的信息，比如树上路径

点分治后，任何路径一定会在某个点分子树内部且经过点分子树根，要么从根结点出发，要么跨过根节点，也就是在点分子树上lca为根

利用这个性质，当我们要统计所有路径的某个信息时，就转化为了在所有点分子树上统计经过根的所有信息，也就是通过点分治固定住了路径的lca

而根据重心的性质，你可以在每个点分子树上跑一个\(O(m\log^k m)\)的算法，这时的总复杂度会只有\(O(n\log^{k+1} n)\)；通常我们需要在每个点分树上做一个dfs(毕竟找重心就要\(O(m)\)了)

点分治模板：

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
std::vector<int> adj[maxn];
bool vis[maxn];

int cent;
int w[maxn];
void dfs1 (int x, int fa) {
    w[x] = 1;
    for (int y : adj[x]) {
        if (y != fa && !vis[y]) {
            dfs1 (y, x);
            w[x] += w[y];
        }
    }
}
void dfs2 (int x, int fa, int sz) {
    bool may_cent = w[x]*2 >= sz;
    for (int y : adj[x]) {
        if (y != fa && !vis[y]) {
            dfs2 (y, x, sz);
            may_cent &= (w[y]*2 <= x);
        }
    }
    if (may_cent) cent = x;
}

void calc (int x);
void solve (int x) {
    dfs1 (x, x);
    dfs2 (x, x, w[x]);
    x = cent;

    calc (x);

    vis[x] = true;
    for (int y : adj[x]) {
        if (!vis[y]) {
            solve (y);
        }
    }
}

例题：点分治模板

题解

在每个点分子树内，维护一个桶存放已经遍历过的所有子树结点的深度，计算新子树时统计所有出现的深度并尝试在桶中匹配询问，最后加到桶里去，就可以保证只算了来自不同子树的两条路径，注意初始桶需要放个0代表从根出发的路径，复杂度\(O(nm\log n)\)

或者对每个根的子树所有结点按照到根节点距离排序，然后双指针一起扫，注意需要检查两个点不能在同一颗子树里，好处是空间复杂度不依赖桶大小，坏处是时间复杂度\(O(n\log^2 n+nm\log n)\)

参考代码：

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
std::vector<std::pair<int, int>> adj;
bool vis[maxn];
int qry[maxm];
bool ans[maxm];
int n, m;

std::vector<bool> buc;
void dfs3 (int x, int fa, int dep, std::vector<int>& ds) {
    if (dep > maxq) return;
    ds.push_back (dep);

    for (auto [y, w] : adj[x]) {
        if (y != fa && !vis[y]) {
            dfs3 (y, x, dep + w);
        }
    }
}
void calc (int x) {
    std::vector<int> dss;
    for (auto [y, w] : adj[x]) {
        std::vector<int> ds;
        dfs3 (y, x, w, ds);

        for (int k = 0; k < m; ++k) {
            if (!ans[k]) {
                for (int d : ds) {
                    if (d <= qry[k] && buc[qry[k] - d]) {
                        ans[k] = true;
                        break;
                    }
                }
            }
        }

        for (int d : ds) {
            buc[d] = true;
            dss.push_back (d);
        }
    }

    for (int d : dss) buc[d] = false;
}
不会淀粉质？

使用树上启发式合并进行逃课~

我们直接在原树的每个结点上做算桶的操作，但是如果直接这么做，构造一个毛毛虫就炸了

所以我们把重儿子的桶转移到父结点上，只要对桶做一个等于距离的平移就可以了，可以提前对桶标记和深度相关的offset

那么轻儿子怎么办？暴力搜就好了，每个结点到根的路径至多只有\(\log n\)个轻边，所以最多只会被暴力\(\log n\)次，复杂度还是\(O(nm\log n)\)

参考代码：

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
std::vector<bool> buc;

void count (int x, int fa, int dep) {
    buc[dep] = true;
    for (auto [y, w] : adj[x]) {
        if (y != fa) {
            count (y, x, dep + w);
        }
    }
}
void clear (int x, int fa, int dep) {
    buc[dep] = false;
    for (auto [y, w] : adj[x]) {
        if (y != fa) {
            clear (y, x, dep + w);
        }
    }
}
void match (int x, int fa, int dep, int rdep) {
    for (int i = 0; i < m; ++i) {
        int bd = qry[i] + rdep*2 - dep;
        if (bd >= 0 && bd <= maxq) ans[i] &= buc[bd];
    }
    for (auto [y, w] : adj[x]) {
        if (y != fa) {
            match (y, x, dep + w, rdep);
        }
    }
}
void solve (int x, int fa, int dep) {
    if (wson[x]) {
        for (auto [y, w] : adj[x]) {
            if (y != fa && y != wson[x]) {
                solve (y, x, dep + w);
                clear (y, x, dep + w);
            }
        }

        solve (wson[x], x, dep + wsw[x]);

        buc[dep] = true;
        for (int i = 0; i < m; ++i) {
            int bd = qry[i] + dep;
            if (bd <= maxq) ans[i] &= buc[bd];
        }

        for (auto [y, w] : adj[x]) {
            if (y != fa && y != wson[x]) {
                match (y, x, dep + w, dep);
                count (y, x, dep + w);
            }
        }
    }
}