前排感谢AgOH大佬 orz orz :【AgOHの算法胡扯】dfs序与树链剖分_哔哩哔哩_bilibili

树的重链剖分本质上就是利用dfs获得树的一个具有较优性质的线性序列。

首先我们知道dfs（或者说树先序遍历）的四条性质：

1.祖先的后代性：任何非树边（变成树之后多出的部分）的两个端点具有祖先后代关系

2.子树的独立性：节点的每个儿子（直接儿子）的子树之间没有边，这是DFS保证的（类似于染色）

3.时间戳的区间性：子树的时间戳为一段区间（连续的一段区间）

4.时间戳的单调性：节点的时间戳小于子树内节点的时间戳

（时间戳指节点的访问顺序。）

看题目：P3384 【模板】重链剖分/树链剖分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先是子树的区间修改，这个问题其实不需要重链剖分，这个很简单：

假设节点x时间戳为t，以x为根的子树节点个数为node_count，由于时间戳的区间性和时间戳的单调性，我们知道这个子树的时间戳范围为 [t,t+node_count-1]，这样我们可以直接利用线段树或者树状数组之类的数据结构进行区间查询和区间修改。

难点在于从节点x到节点y的最短路径这条链上的查询和修改，如果暴力，显然时间复杂度是O(n)，因为题目所给树是一个链是一个很方便的卡时间方法。

下面就是重链剖分：

1.一个节点不是重节点就是轻节点

2.根节点为轻节点

3.一个节点x如果是重节点 等价于 节点x是所有兄弟节点中子树节点个数最多的那一个。否则为轻节点。

4.以轻节点为头，优先沿着重节点一路向下，会得到一个时间戳连续的链，称这个链为重链。

根据上面四个性质，我们显然可以发现：

1.一个节点只要有儿子，就一定有重儿子

2.一个节点是轻节点那么他一定是一个重链的开始

3.一般来说重节点多而轻节点少

利用重链时间戳的连续性，可以记录下 top[x] 表示一个节点所在重链的起点，然后快速跳跃，实现快速的查询和修改：时间复杂度:O(logn)具体证明可搜索。

下面是代码，交上去即可AC。

洛谷P3384 AC代码：

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

const int maxn=1e5+10;

vector<int> graph[maxn];//邻接表

struct NODE{
    int fa,son,node_count,depth;
    int dfn,top,w;
}node[maxn];

//first是和，second是lazy tag
pair<int,int> tree[maxn<<2];

int n,m,root,mod,tim,weight[maxn];

//第一次填上 depth，fa和node_count并找到重儿子
void dfs1(int now,int fa)
{
    node[now].fa=fa;
    node[now].depth=node[fa].depth+1;
    node[now].node_count=1;

    int maxsize=-1;

    for(const auto&it:graph[now])
    {
        if(it==fa)continue;
        dfs1(it,now);

        node[now].node_count+=node[it].node_count;

        if(node[it].node_count>maxsize)
        {
            maxsize=node[it].node_count;
            node[now].son=it;
        }
    }
}

//t表示top，
void dfs2(int now,int t)
{
    node[now].dfn=++tim;
    node[now].top=t;
    weight[tim]=node[now].w;

    //如果没有重儿子，说明到叶子结点了，返回
    if(node[now].son==0)return;

    //先走重儿子
    dfs2(node[now].son,t);

    //下面走轻儿子 
    for(const auto&it:graph[now])
    {
        if(it==node[now].son||
            it==node[now].fa)
            continue;
        
        //路线的第一个为轻儿子
        dfs2(it,it);
    }
}

void pushup(pair<int,int>&x,pair<int,int>&l,pair<int,int>&r)
{
    x.first=(l.first+r.first)%mod;
}

void pushdown(int now,int l,int r)
{
    int mid=l+r>>1;

    tree[now<<1].second+=tree[now].second;
    tree[now<<1|1].second+=tree[now].second;

    tree[now<<1].first+=(mid-l+1)*tree[now].second%mod;
    tree[now<<1|1].first+=(r-mid)*tree[now].second%mod;

    tree[now].second=0;
}

void build(int now,int l,int r)
{
    tree[now].second=0;
    if(l==r)
    {
        tree[now].first=weight[l];
        return;
    }

    int mid=l+r>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    pushup(tree[now],tree[now<<1],tree[now<<1|1]);
}

int query(int now,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)
        return tree[now].first;

    int mid=l+r>>1,ans=0;

    pushdown(now,l,r);

    if(mid>=L)
        ans=(ans+query(now<<1,l,mid,L,R))%mod;
    
    if(mid<R)
        ans=(ans+query(now<<1|1,mid+1,r,L,R))%mod;
    
    return ans;
}

void modify(int now,int l,int r,int L,int R,int k)
{
    if(l>=L&&r<=R)
    {
        tree[now].first+=(r-l+1)*k;
        tree[now].second+=k;
        return;
    }

    int mid=l+r>>1;
    pushdown(now,l,r);

    if(mid>=L)
        modify(now<<1,l,mid,L,R,k);
    if(mid<R)
        modify(now<<1|1,mid+1,r,L,R,k);

    pushup(tree[now],tree[now<<1],tree[now<<1|1]);
}

void modifytree(int now,int k)
{
    modify(1,1,n,node[now].dfn,
        node[now].dfn+node[now].node_count-1,k);
}

int querytree(int now)
{
    return query(1,1,n,node[now].dfn,
        node[now].dfn+node[now].node_count-1);
}

void modifychain(int x,int y,int k)
{
    k%=mod;

    while(node[x].top!=node[y].top)
    {
        if(node[node[x].top].depth<
            node[node[y].top].depth)
            swap(x,y);
        
        //这里是 dfn[top[x]] ，弄错了一次，怎么找都没找到。一直错。
        modify(1,1,n,node[node[x].top].dfn,node[x].dfn,k);
        x=node[node[x].top].fa;
    }

    if(node[x].dfn>node[y].dfn)
        swap(x,y);
    
    modify(1,1,n,node[x].dfn,node[y].dfn,k);
}

int querychain(int x,int y)
{
    int ans=0;

    while(node[x].top!=node[y].top)
    {
        if(node[node[x].top].depth<
            node[node[y].top].depth)
            swap(x,y);
        
        ans=(ans+query(1,1,n,node[node[x].top].dfn,node[x].dfn))%mod;
        x=node[node[x].top].fa;
    }

    if(node[x].dfn>node[y].dfn)
        swap(x,y);
    
    ans=(ans+query(1,1,n,node[x].dfn,node[y].dfn))%mod;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif

//-------------------------------------------------

    cin>>n>>m>>root>>mod;

    for(int i=1;i<=n;++i)
        cin>>node[i].w;
    

    for(int i=1,x,y;i<n;++i)
    {
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs1(root,root);
    dfs2(root,root);

    build(1,1,n);

    int x,y,z,op;

    while(m--)
    {
        cin>>op>>x;

        if(op==4)
        {
            cout<<querytree(x)%mod<<'\n';
            continue;
        }
        cin>>y;

        if(op==3)
        {
            modifytree(x,y);
            continue;
        }
        else if(op==2)
        {
            cout<<querychain(x,y)%mod<<'\n';
            continue;
        }

        cin>>z;

        modifychain(x,y,z);
    }

//-------------------------------------------------

#ifdef LOCAL
    cout << "Time Used:\n" << clock() - c1 << " ms" << endl;
#endif

    //system("pause");
    return 0;
}

点击并拖拽以移动

课后小作业：P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码：

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
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

const int maxn=500000+10;

vector<int> graph[maxn];
int n,m,root;
int top[maxn],fa[maxn],son[maxn],node_count[maxn],depth[maxn];

void dfs1(int now,int f)
{
    depth[now]=depth[f]+1;
    fa[now]=f;
    node_count[now]=1;

    int maxsize=-1;

    for(const auto&it : graph[now])
    {
        if(it==f)continue;
        dfs1(it,now);

        node_count[now]+=node_count[it];

        if(node_count[it]>maxsize)
        {
            son[now]=it;
            maxsize=node_count[it];
        }
    }
}

void dfs2(int now,int t)
{
    top[now]=t;

    if(son[now]==0)
        return;

    dfs2(son[now],t);

    for(const auto&it : graph[now])
    {
        if(it==fa[now]||it==son[now])
            continue;
        
        dfs2(it,it);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
            swap(x,y);
        
        x=fa[top[x]];
    }

    return depth[x]<depth[y]?x:y;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif

//-------------------------------------------------

    cin>>n>>m>>root;

    for(int i=1,x,y;i<n;++i)
    {
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    dfs1(root,root);
    dfs2(root,root);
    int x,y;
    while(m--)
    {
        cin>>x>>y;
        cout<<lca(x,y)<<'\n';
    }

//-------------------------------------------------

#ifdef LOCAL
    cout << "Time Used: " << clock() - c1 << " ms" << endl;
#endif

    //system("pause");
    return 0;
}

点击并拖拽以移动