树链剖分
|
1.7k 字
|
8 分钟

树剖

一个神奇的数据结构

树链剖分，顾名思义就是把一棵树解剖成一些链

我们先来几个定义：

重儿子：对于一个节点来说，他的儿子们中子树体积最大的儿子称为他的重儿子

重边：两个重儿子连起来的边

重链：很多条重边连起来形成的一条链

轻儿子：除了重儿子之外的儿子

轻链：类比一下

我们会发现，重儿子是可以一遍dfs求出来的，我们会发现一个很重要的性质：

在dfs序中，重链的节点都是相邻的

那么我们就可以在这个dfs序上面进行一点点数据结构对吧

然后，我们还可以发现，如果对于两个点之间的距离来说，如果他们两个在同一条重链上面，就可以求lca

这可以对于一些关于路径的东西进行求解

路径就可以直接多次向上跳重链

既然是板子就放个代码？

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e5 + 10;

int n, m, root, mod;
int dep[maxn], son[maxn], siz[maxn], f[maxn], cnt, dfn[maxn], top[maxn];
int a[maxn];
int head[maxn], tot;

struct node
{
    int y, nex;
} e[maxn * 2];

struct tree
{
    int val, add;
} t[maxn * 4];

void add(int x, int y)
{
    e[++tot] = {y, head[x]};
    head[x] = tot;
}

void pushup(int rt)
{
    t[rt].val = (t[rt << 1].val + t[rt << 1 | 1].val) % mod;
}

void pushdown(int rt, int l, int r)
{
    if (t[rt].add)
    {
        int mid = l + r >> 1;
        (t[rt << 1].add += t[rt].add) %= mod, (t[rt << 1 | 1].add += t[rt].add) %= mod;
        (t[rt << 1].val += (mid - l + 1) * t[rt].add) %= mod;
        (t[rt << 1 | 1].val += (r - mid) * t[rt].add) %= mod;
        t[rt].add = 0;
    }
    return;
}

void change(int rt, int l, int r, int x, int y, int val)
{
    if (x <= l && y >= r)
    {
        t[rt].val += (r - l + 1) * val;
        (t[rt].add += val) %= mod;
        return;
    }
    pushdown(rt, l, r);
    int mid = l + r >> 1;
    if (x <= mid)
        change(rt << 1, l, mid, x, y, val);
    if (y > mid)
        change(rt << 1 | 1, mid + 1, r, x, y, val);
    pushup(rt);
    return;
}

int query(int rt, int l, int r, int x, int y)
{
    if (x > r || y < l)
        return 0;
    if (x <= l && y >= r)
        return t[rt].val;
    pushdown(rt, l, r);
    int mid = l + r >> 1;
    return (query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y)) % mod;
}

void dfs1(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    siz[x] = 1;
    f[x] = fa;
    int maxx = 0;
    for (int i = head[x]; i; i = e[i].nex)
    {
        int v = e[i].y;
        if (v == fa)
            continue;
        dfs1(v, x);
        if (siz[v] > maxx)
            son[x] = v, maxx = siz[v];
        siz[x] += siz[v];
    }
    return;
}

void dfs2(int x, int fa, int _top)
{
    dfn[x] = ++cnt;
    top[x] = _top;
    change(1, 1, n, dfn[x], dfn[x], a[x]);
    if (son[x])
        dfs2(son[x], x, _top);
    for (int i = head[x]; i; i = e[i].nex)
    {
        int v = e[i].y;
        if (v == fa || v == son[x])
            continue;
        dfs2(v, x, v);
    }
    return;
}

void change_line(int x, int y, int val)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        change(1, 1, n, dfn[top[x]], dfn[x], val);
        x = f[top[x]];
    }
    if (dep[x] < dep[y])
        swap(x, y);
    change(1, 1, n, dfn[y], dfn[x], val);
    return;
}

int query_line(int x, int y)
{
    int res = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        res += query(1, 1, n, dfn[top[x]], dfn[x]);
        x = f[top[x]];
    }
    if (dep[x] < dep[y])
        swap(x, y);
    res += query(1, 1, n, dfn[y], dfn[x]);
    return res % mod;
}

void change_tree(int x, int val)
{
    change(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, val);
}

int query_tree(int x)
{
    return query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin >> n >> m >> root >> mod;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(root, 0);
    dfs2(root, 0, root);
    while (m--)
    {
        int op, x, y, z;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y >> z;
            change_line(x, y, z);
        }
        else if (op == 2)
        {
            cin >> x >> y;
            cout << query_line(x, y) << endl;
        }
        else if (op == 3)
        {
            cin >> x >> y;
            change_tree(x, y);
        }
        else
        {
            cin >> x;
            cout << query_tree(x) << endl;
        }
    }
    return 0;
}

P3384 【模板】轻重链剖分/树链剖分

模板就像是上面说的一样用线段树维护一下就好了

我们考虑如果是路径的话，我们就x一直向上跳重链的顶部，然后区间求和最大……等等

y同理

一直到两个点都在同一条重链上的时候我们就再做一次区间求和最大就好了

总体复杂度两个log一个log是树剖，另一个是线段树，所以常数并没有说多么小

P3313 [SDOI2014]旅行

我们对于每一个宗教都开一个线段树，接下来的就像模板一样求就好了

但是不仅仅是这样，因为空间会炸

所以需要动态开点

P2590 [ZJOI2008]树的统计

不就是个板子……甚至比上面的板子还简单？

P1505 [国家集训队]旅游

边权转点权，然后树剖

边权转点权是一个非常经典的套路，首先对于一棵树上面，边权应该下放到深度较深的那个点的点权上面，然后在查询的时候，会发现如果把所有的点权都加上的话，lca的点权应该是lca到lca父亲的边权，这是多余的东西，我们应该把他删掉，所以特判一下就好了

P2486 [SDOI2011]染色

首先考虑如果在一个序列上面应该怎么做

如果在一个序列上面，我们就应该用线段树进行一下维护，维护的过程中，合并的时候就判断一下连接点的颜色是不是一样就好了，我们看连接点的颜色的时候是需要记录一下线段树区间的做右端点的颜色的

那么转化到树上也是一样的道理

如果说树剖的时候跳到了重链的顶部，因为每一次跳的时候都会跳到重链顶部的父亲节点，我们只需要判断一下这两个节点的颜色是不是一样就好了

P4211 [LNOI2014]LCA

很经典的套路：把路径转化成边相加

我们会发现，如果说一个结点的深度dep，我们可以把它转化成向上跳dep-1次，也就可以转化成，祖先有dep个点，就把这dep个点每一个点权加一，然后求“区间”和

连续的一段点权改变就可以直接树剖了

我们把操作全部离线下来，离线下来之后，把所有的查询操作按照右端点排序，既然是查询l-r这个区间之内的贡献，我们就可以直接查询1-r和1-(l-1)的贡献然后相减

这就可以离线，每一次都把这个点到根的路径点权加一，然后树剖求和

上一篇
下一篇