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

粥2414 · 2025-04-29 09:17:07 · 题解

前置知识

dfs 序。
线段树或树状数组。
图的存储。
lca 相关知识。（不一定要会求但一定要了解）
树链剖分

看到这题，一眼~~树状数组模板题~~。然而是树上，那怎么办？

有没有一种算法可以将在树上的问题转换为序列上的问题呢？

有的兄弟，有的，那就是树链剖分。

简介

树链剖分就是通过将树剖分成一条一条的链，将其转化为序列问题的算法。有了树链剖分，就可以将很多原本只能运用于序列上的数据结构用于树上。

用处

先说明用处，方便理解。

首先需要明确几个概念：

重儿子：一个节点的儿子中，拥有最大子树的那个叫做重儿子，其余的是轻儿子。如果子树大小相同，取任意一个即可。
重链：由根节点（可以是子树根节点）的重子孙组成的一条链。特别地，单独的一个节点也可视为重链。
轻边，轻链的定义类似。

如图所示的即为一棵树的重链：

划分的方式可能不唯一。

树链剖分可以很方便地解决两点间简单路径上的操作。

对于本题的操作 3、4，普通的 dfs 序便可解决，原理是 dfs 序保证一个节点的子树节点全在这个节点后面的一段连续区间，套个数据结构即可。

而对于前两个操作，普通 dfs 序就不行了。它没法保证两点间简单路径的连续性。这时就可以用树链剖分解决。

原理

树链剖分就是一种特殊的 dfs 序，它保证一个节点的子树，以及它所在的重链在一个连续的区间内。如果要操作的区间在一个重链内，那么直接操作即可；如果要操作的简单路径跨了多个重链，那么可以先修改当前重链，然后跳到当前重链顶部的父节点，循环往复，直到两个节点的 lca。

实现

其代码主体就是两个 dfs。

第一个 dfs 预处理出节点 i 的父节点 fa_i，深度 dep_i，子树大小 siz_i，重儿子 son_i

代码

 void dfs1(ll now, ll fat) {
    fa[now] = fat;
    dep[now] = dep[fat] + 1;
    siz[now] = 1;
    for (rint i = h[now]; i; i = lian[i].ne) {
        ll to = lian[i].to;
        if (to != fat) {
            dfs1(to, now);
            siz[now] += siz[to];
            if (siz[to] > siz[son[now]])son[now] = to;
        }
    }
}

第二个 dfs 预处理出每个节点对应的 dfs 序和 dfs 序对应的初值，以及一条重链的顶端节点编号。

如何保证重链在一起？优先递归重儿子即可。

代码

 void dfs2(ll now, ll ftop) {//ftop 为重链顶端
    dfss[now] = ++dcnt;
    dv[dfss[now]] = v[now];
    top[now] = ftop;
    if (son[now])dfs2(son[now], ftop);//优先递归重儿子，在一条重链上，顶端相同。
    for (rint i = h[now]; i; i = lian[i].ne) {
        ll to = lian[i].to;
        if (to != fa[now] && to != son[now])dfs2(to, to);//新的重链，顶端为它自己
    }
}

具体操作

这样，树链剖分就完成了。接下来是数据结构部分了。

对于节点 x 子树上的操作，只需要对区间 [x,x+siz_x-1] 进行操作即可。

对于点 x,y 之间简单路径上的操作，则要麻烦一点。步骤如下：

判断两个点是否在一条重链上，即重链顶部是否相等。如果相等，修改区间 [x,y] 即可；否则，进行第二步。
如果 dep_{top_x}<dep_{top_y}，那么交换 x,y。这一步是保证向上跳时不会跳过 lca。
修改区间 [top_x,x]，然后令 x\gets fa_{top_x}。注意顶端节点的 dfs 序较小，要在前面。
回到步骤 1。
正确性证明

这样会不会修改多余的节点呢？答案是否定的。

我们假设节点 y 在 lca 所在重链，且点 x 不在，那么 x 一定在 lca 的某个轻儿子的子树上。由于此时 x 所在重链顶端高度一定低于 y，所以一定优先让 x 向上跳，最终会跳到 lca 某个轻儿子为顶端的重链上，然后 x 就会变成 lca，直接修改，不会影响其他节点。

如果两个儿子都不在 lca 所在重链，那么在向上跳的过程中，必然会有一个儿子先到达 lca 所在重链，回归上文情况。

复杂度分析

两遍 dfs 复杂度 O(n)，树状数组或线段树复杂度 O(n\log n)，向上跳的过程中每穿越一条树链，那么就相当于经过了一个节点的轻边，由于重儿子的子树大小一定大于等于它，所以其子树大小至少会变为原来的二倍，所以最坏时间复杂度 O(\log n)，实际可能更小。

总复杂度 O(n\log^2 n)。

完整代码

线段树在我校 oj 上~~由于评测机太烂~~需要严重卡常，所以我使用树状数组进行维护，洛谷上两者皆可正常通过。

//#define LH
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define ll long long
#define rint register int
namespace DHW {
#ifdef LH
    char buf[1 << 20],*p1 = buf,*p2 = buf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++);
#endif
     ll read() {
        ll f = 1, x = 0;
        char ch = getchar();
        while (ch < 48 || ch > 57) {
            if (ch == '-')f = -1;
            ch = getchar();
        }
        while (ch >= 48 && ch <= 57) {
            x = x * 10 + ch - 48;
            ch = getchar();
        }
        return x * f;
    }
     void write(ll x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9)write(x / 10);
        putchar(x % 10 + 48);
    }
#ifdef LH
    #undef getchar
#endif
} using namespace DHW;
ll qp(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
const ll N = 1e5+9;
ll n, m, r, p;
ll tr1[N], tr2[N];
struct LIAN {
    ll to, ne;
} lian[N * 2];
ll h[N], lcnt;
ll dep[N], fa[N], dfss[N], son[N], dcnt, top[N], siz[N];
ll v[N], dv[N];
 void add(ll u, ll v) {
    lian[++lcnt].to = v;
    lian[lcnt].ne = h[u];
    h[u] = lcnt;
}
 ll lowbit(ll x) {
    return x & (-x);
}
 void tr_add(ll x, ll v) {
    rint i = x;
    while (i <= n) {
        tr1[i] = (tr1[i] + v)  ;
        tr2[i] = (tr2[i] + (v * x)  )  ;
        i += lowbit(i);
//      cout<<i<<' ';
    }
}
 ll tr_qu(ll r) {
    ll i = r, ans = 0;
    while (i > 0) {
        ans += (((r + 1) * tr1[i])   - tr2[i]  )  ;
        i -= lowbit(i);
    }
    return ans  ;
}
 void dfs1(ll now, ll fat) {
    fa[now] = fat;
    dep[now] = dep[fat] + 1;
    siz[now] = 1;
    for (rint i = h[now]; i; i = lian[i].ne) {
        ll to = lian[i].to;
        if (to != fat) {
            dfs1(to, now);
            siz[now] += siz[to];
            if (siz[to] > siz[son[now]])son[now] = to;
        }
    }
}
 void dfs2(ll now, ll ftop) {
//  if(now==4)cout<<"dhwzs";
    dfss[now] = ++dcnt;
    dv[dfss[now]] = v[now];
    top[now] = ftop;
    if (son[now])dfs2(son[now], ftop);
    for (rint i = h[now]; i; i = lian[i].ne) {
        ll to = lian[i].to;
        if (to != fa[now] && to != son[now])dfs2(to, to);
    }
}
 void do_add1(ll x, ll y, ll z) { //操作1
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        tr_add(dfss[top[x]], z);
        tr_add(dfss[x] + 1, -z);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y])swap(x, y);
    tr_add(dfss[y], z);
    tr_add(dfss[x] + 1, -z);
}
 void do_add3(ll x, ll z) { //操作3
//  cout<<x<<' '<<dfss[x]<<endl;
    tr_add(dfss[x], z);
    tr_add(dfss[x] + siz[x], -z);
}
 ll do_qu2(ll x, ll y) { //操作2
    ll ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        ans += (tr_qu(dfss[x])  - tr_qu(dfss[top[x]] - 1) )  ;
        ans %= p;
        x = fa[top[x]];
    }
    if (dep[x] < dep[y])swap(x, y);
    ans += (tr_qu(dfss[x])  - tr_qu(dfss[y]-1) );
    return ans;
}
 ll do_qu4(ll x) { //操作4
    return (tr_qu(dfss[x] + siz[x] - 1)   - tr_qu(dfss[x] - 1)  )  ;
}
void dfs3(ll now, ll fat) {
    cout<<dfss[now]<<' '<<v[now]<<' '<<siz[now]<<' '<<now<<endl; 
    for (rint i = h[now]; i; i = lian[i].ne) {
        ll to = lian[i].to;
        if (to != fat) {
            dfs3(to, now);
        }
    }
}
int main() {
    n = read();
    m = read();
    r = read();
    p = read();
    for (rint i = 1; i <= n; i++) {
        v[i] = read();
    }
    for (rint i = 1; i < n; i++) {
        ll u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    dfs1(r, 0);
    dfs2(r, r);
    for (rint i = 1; i <= n; i++) {
        tr_add(i, dv[i]);
        tr_add(i + 1, -dv[i]);
    }
    for (rint i = 1; i <= m; i++) {
        ll op = read(), x = read();
        if (op == 1) {
            ll y = read(), z = read();
            do_add1(x, y, z);
        }
        if (op == 2) {
            ll y = read();
            write(do_qu2(x, y)%p);
            putchar('\n');
        }
        if (op == 3) {
            ll z = read();
            do_add3(x, z);
        }
        if (op == 4) {
            write(do_qu4(x)%p);
            putchar('\n');
        }
    }
//  dfs3(r,0);
//  for(int i=1;i<=n+1;i++){
//      cout<<tr1[i]<<' '<<tr2[i]<<endl;
//  }
    return 0;
}

其他运用

由上文两点向上跳的过程可以很显然地看出，树剖还可用于求 lca，常数貌似是比朴素的倍增求 lca 要小的。（~~黄题蓝做~~，不再赘述）