Dyd's Blog

He who has a strong enough why can bear almost any how.

树链剖分

Posted on Edited on In
Symbols count in article: 5.1k Reading time ≈ 5 mins.

线段树进化！

树链剖分

预备知识

线段树，DFS序

概念

树链剖分的核心思想是将一棵树的节点重新排序，再将树转换为一个序列，使得树上的任意一条路径可以被最多 $\log{n}$ 段区间表示出来，由此我们可以将树上的路径操作化为区间操作。

定义

  • 重儿子（节点）：子树结点数目最多的结点

  • 轻儿子（节点）：除了重儿子以外的结点

  • 重边：父亲结点和重儿子连成的边

  • 轻边：父亲节点和轻儿子连成的边

  • 重链：由多条重边连接而成的路径，如果一个点没连接重边，那该节点也可以是一条重链

  • 轻链：由多条轻边连接而成的路径

如图：
例子
可以看到：对于节点1，节点4的子树的节点比2,3的多，所以4是重儿子，对于4节点9的子树的节点比8,9的多，所以9是重儿子，以此类推，图中黑色的节点是重儿子，其余的节点是轻儿子。

红边是重边，黑边是轻边

1 - 4 - 9 - 13 - 14；
8；
10；
3 - 7；
2 - 6 - 11；
5；都是重链

我们发现：叶节点没有重儿子，非叶节点有且只有1个重儿子

但要注意，并不是轻儿子之后全是轻儿子，比如2后面就有6和11两个重儿子，也就是说，当一个节点选了他的重儿子之后，我们并不能保证它的轻儿子就是叶节点，所以我们就以这个轻儿子为根，再去选这个轻儿子的轻重儿子

化树为列

我们先用dfs序来实现将树化为序列，但dfs时我们优先搜索重儿子，这样的好处是可以保证一段重链在区间上是连续的，如上面的图上，dfs序应为：1-4-9-13-14-8-10-3-7-2-6-11-5

那么一条路径就可以拆分成最多 $\log{n}$ 条重链，对应到序列上是最多 $\log{n}$ 个区间。

现在，问题就是如何找到一条路径对应的区间。

寻找区间

对于节点 $x,y$ 若要求 $x$ 到 $y$ 的路径对应的区间，可以用如下方法：

  1. 找到 $x,y$ 中所在重链的顶点较低的点（即层数较深的点），不妨设为 $x$ ，并设 $x$ 所在重链顶点为 $z$

  2. 对区间 $[z,x]$ 操作，更新 $x$ 为 $z$ 的父节点

  3. 重复2、3步，直到 $x,y$ 在同一条重链上（这条重链一定是它们的最近公共祖先所在重链）

  4. 对区间 $[x,y]$ （或 $[y,x]$ ）操作即可

如上面的图中，要找节点13到节点5的路径，可以让 $x=13$ , $y=5$ 过程如下：

  1. 第一步后，找到较低的点是 $y=5$ ，顶点 $z=5$

  2. 第二步，操作区间 $[z,y]=[5,5]$ ，更新 $y=2$

  3. 第三步，重复，操作区间 $[z,y]=[2,2]$ ，更新 $y=1$

  4. 第五步, $x,y$ 已在一条重链上，操作区间 $[y,x]=[1,13]$

一般来说，对于每个区间，我们用线段树、分块等方式去维护，最多有 $\log{n}$ 个区间，故一般时间复杂度为 $O(log^2{n})$

例题

P3384
代码如下：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,m,root,p;
struct Edge{
    int ver,ne;
}e[N*2];
int h[N],idx=0,w[N];
int id[N],nw[N],cnt=0; //id:节点在dfs序中的编号,nw:dfs序列每个编号对应的权值
int dep[N],size[N],top[N],fa[N],h_son[N]; //dep:节点深度,size:节点为根的子
                                          //树的大小,top:节点所在重链的顶点
                                          //fa:父节点,h_son:重儿子
struct ST{
    int l,r;
    LL add,sum;
}tr[N*4];
void add(int x,int y){
    e[idx].ver=y,e[idx].ne=h[x],h[x]=idx++;
}
void dfs1(int x,int father,int depth){ //求每个的重儿子
    dep[x]=depth;
    fa[x]=father;
    size[x]=1;
    for(int i=h[x];i!=-1;i=e[i].ne){
        int y=e[i].ver;
        if(y==father) continue;
        dfs1(y,x,depth+1);
        size[x]+=size[y];
        if(size[h_son[x]]<size[y]) h_son[x]=y;
    }
}
void dfs2(int x,int t){ //求dfs序,t:当前节点所在重链的顶点
    id[x]=++cnt;
    nw[cnt]=w[x];
    top[x]=t;
    if(!h_son[x]) return ; //若是叶节点,直接返回
    dfs2(h_son[x],t);
    for(int i=h[x];i!=-1;i=e[i].ne){
        int y=e[i].ver;
        if(y==fa[x]||y==h_son[x]) continue;
        dfs2(y,y); //轻儿子一定是其所在重链的顶点
    }
}
void push_up(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].sum%=p;
}
void push_down(int u){
    if(tr[u].add){
        tr[u<<1].add+=tr[u].add;
        tr[u<<1].add%=p;
        tr[u<<1].sum+=tr[u].add*(tr[u<<1].r-tr[u<<1].l+1);
        tr[u<<1].sum%=p;
        tr[u<<1|1].add+=tr[u].add;
        tr[u<<1|1].add%=p;
        tr[u<<1|1].sum+=tr[u].add*(tr[u<<1|1].r-tr[u<<1|1].l+1);
        tr[u<<1|1].sum%=p;
        tr[u].add=0;
    }
}
void build(int u,int l,int r){
    tr[u].l=l;
    tr[u].r=r;
    tr[u].add=0;
    if(l==r){
        tr[u].sum=nw[r];
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}
void modify(int u,int l,int r,int k){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].add+=k;
        tr[u].add%=p;
        tr[u].sum+=k*(tr[u].r-tr[u].l+1);
        tr[u].sum%=p;
        return ;
    }
    push_down(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,k);
    if(r>mid) modify(u<<1|1,l,r,k);
    push_up(u);
}
LL ask(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    push_down(u);
    int mid=tr[u].l+tr[u].r>>1;
    LL res=0;
    if(l<=mid) res+=ask(u<<1,l,r),res%=p;
    if(r>mid) res+=ask(u<<1|1,l,r),res%=p;
    return res;
}
void modify_path(int u,int v,int k){
    while(top[u]!=top[v]){  //当这两个点不在同一重链
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,id[top[u]],id[u],k); //注意在dfs序中top[u]在u前面
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    modify(1,id[v],id[u],k);
}
LL ask_path(int u,int v){
    LL res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=ask(1,id[top[u]],id[u]);
        res%=p;
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    res+=ask(1,id[v],id[u]);
    return res%p;
}
void modify_tree(int u,int k){
    modify(1,id[u],id[u]+size[u]-1,k); //在dfs序中,以一个节点为根的子树一定
                                       //跟在这个节点后面
}
LL ask_tree(int u){
    return ask(1,id[u],id[u]+size[u]-1);
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&root,&p);
    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
        w[i]%=p;
    }
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(root,-1,1);
    dfs2(root,root);
    build(1,1,cnt);
    while(m--){
        int op,u,v,k;
        scanf("%d%d",&op,&u);
        if(op==1){
            scanf("%d%d",&v,&k);
            modify_path(u,v,k);
        }
        else if(op==2){
            scanf("%d",&v);
            printf("%lld\n",ask_path(u,v));
        }
        else if(op==3){
            scanf("%d",&k);
            modify_tree(u,k);
        }
        else{
            printf("%lld\n",ask_tree(u));
        }
    }
    return 0;
}