树链剖分 洛谷P3384模板题

发表于 | 更新于:

树剖，树剖好吃吗？

这里是树链剖分

小菜鸡在长时间划水之后终于似乎看懂了树链剖分(⁄ ⁄•⁄ω⁄•⁄ ⁄)
部分转自 ivanovcraft带师 和 百度百科。

概念

（悄悄说）之前看了好多好多博客，大概只是知道树链剖分的实现，但并不了解树链剖分存在的意义……
（继续悄悄说）所以毛毛雨去查了一下百度百科(⁄ ⁄•⁄ω⁄•⁄ ⁄)，感觉百度百科简直是良心定义！！

以下内容摘自百度百科

  • 树路径信息维护算法。
  • 将一棵树划分成若干条链，用数据结构（树状数组、BST、SPLAY、线段树等）去维护每条链，
    复杂度为O(logN)。
  • 其实本质是一些数据结构/算法在树上的推广

以后数据结构不仅仅可以维护线段，还可以用来维护树啦！！
（有点像从一维升级成二维了诶！）

一些基本定义

  • 重结点：子树结点数目最多的结点；
  • 轻节点：父亲节点中除了重结点以外的结点；
  • 重边：父亲结点和重结点连成的边；
  • 轻边：父亲节点和轻节点连成的边；
  • 重链：由多条重边连接而成的路径；
  • 轻链：由多条轻边连接而成的路径；


如图加粗的链为重链，标红点的为重链起点（即下文的top值）。
下面是个人理解（溜）：重链为最长链，所有节点都能跳到重链上，并且跳的次数最少。其实随便选链进行剖分也是可以的，但选重链是最方便的~
然后有一些奇奇怪怪的性质：

  • 轻边(u,v)，size(v)<=size(u)/2。
  • 从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。

实现过程

定义

要实现树链剖分，要记录下面的值

名称 解释
f[u] 保存结点u的父亲节点
d[u] 保存结点u的深度值
size[u] 保存以u为根的子树节点个数
son[u] 保存重儿子
rk[u] 保存当前dfs标号在树中所对应的节点
top[u] 保存当前节点所在链的顶端节点
id[u] 保存树中每个节点剖分以后的新编号（DFS的执行顺序）

预处理

实现方式是进行两遍dfs
第一遍：

  • 对于一个点，求出他所在子树大小，并找到它的重儿子（size、son数组）
  • 记录它的父亲及深度（f、d数组）

第二遍：

  • 连接重链，同时标记每一个节点的dfs序，并且为了用数据结构来维护重链，我们在dfs时保证一条重链上各个节点dfs序连续（即处理出数组top,id,rk）

操作

  • 如果两点位于不同重链，则将深度大的节点跳到所在重链顶端，并用数据结构维护这条重链的信息，然后沿轻链跳到当前节点的父亲节点。
  • 如果两点位于同一重链，则统计这两点之间的信息。

然后一起来看题目鸭！

下面是愉快的贴代码部分啦QWQ
题目是洛谷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
168
169
170
171
172
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll maxn=1e5+10;
struct edge{
    ll next,to;
}e[maxn*2];
struct node{
    ll l,r,ls,rs,sum,lazy;
}a[maxn*2];
ll n,m,r,rt,mod,v[maxn],head[maxn],cnt,f[maxn],d[maxn],son[maxn],size[maxn],top[maxn],id[maxn],rk[maxn];
void add(ll x,ll y)
{
    e[++cnt].next=head[x];
    e[cnt].to=y;
    head[x]=cnt;
}
void dfs1(ll u,ll fa,ll depth)    //当前节点、父节点、层次深度
{
    f[u]=fa;
    d[u]=depth;
    size[u]=1;    //这个点本身size=1
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].to;
        if(v==fa)
            continue;
        dfs1(v,u,depth+1);    //层次深度+1
        size[u]+=size[v];    //子节点的size已被处理，用它来更新父节点的size
        if(size[v]>size[son[u]])
            son[u]=v;    //选取size最大的作为重儿子
    }
}
void dfs2(ll u,ll t)    //当前节点、重链顶端
{
    top[u]=t;
    id[u]=++cnt;    //标记dfs序
    rk[cnt]=u;    //序号cnt对应节点u
    if(!son[u])
        return;
    dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].to;
        if(v!=son[u]&&v!=f[u])
            dfs2(v,v);    //一个点位于轻链底端，那么它的top必然是它本身
    }
}
inline void pushup(ll rt)
{
    a[rt].sum=(a[a[rt].ls].sum+a[a[rt].rs].sum)%mod;
}
void build(ll l,ll r,ll x)
{
    if(l==r)
    {
        a[x].sum=v[rk[l]];
        a[x].l=a[x].r=l;
        return;
    }
    ll mid=l+r>>1;
    a[x].ls=cnt++; a[x].rs=cnt++;
    build(l,mid,a[x].ls); build(mid+1,r,a[x].rs);
    a[x].l=a[a[x].ls].l; a[x].r=a[a[x].rs].r;
    pushup(x);
}
inline ll len(ll x)
{
    return a[x].r-a[x].l+1;
}
inline void pushdown(ll x)
{
    if(a[x].lazy)
    {
        ll ls=a[x].ls,rs=a[x].rs,lz=a[x].lazy;
        (a[ls].lazy+=lz)%=mod,(a[rs].lazy+=lz)%=mod;
        (a[ls].sum+=lz*len(ls))%=mod,(a[rs].sum+=lz*len(rs))%=mod;
        a[x].lazy=0;
    }
}
void update(ll l,ll r,ll c,ll x)
{
    if(a[x].l>=l&&a[x].r<=r)
    {
        (a[x].lazy+=c)%=mod,(a[x].sum+=len(x)*c)%=mod;
        return;
    }
    pushdown(x);
    ll mid=a[x].l+a[x].r>>1;
    if(mid>=l)
        update(l,r,c,a[x].ls);
    if(mid<r)
        update(l,r,c,a[x].rs);
    pushup(x);
}
ll query(ll l,ll r,ll x)
{
    if(a[x].l>=l&&a[x].r<=r)
        return a[x].sum;
    pushdown(x);
    ll mid=a[x].l+a[x].r>>1,tot=0;
    if(mid>=l)
        tot+=query(l,r,a[x].ls);
    if(mid<r)
        tot+=query(l,r,a[x].rs);
    return tot%mod;
}
inline ll sum(ll x,ll y)
{
    ll ret=0;
    while(top[x]!=top[y]) //两点不在同一条重链
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ret+=query(id[top[x]],id[x],rt);
        ret%=mod;
        x=f[top[x]];
    }
    //循环结束，两点位于同一重链上，但两点不一定为同一点，所以我们还要统计这两点之间的贡献
    if(id[x]>id[y]) swap(x,y);
    return (ret+query(id[x],id[y],rt))%mod;
}
inline void updates(ll x,ll y,ll c)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        update(id[top[x]],id[x],c,rt);
        x=f[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    update(id[x],id[y],c,rt);
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&r,&mod);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(ll i=1;i<n;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    cnt=0,dfs1(r,0,1),dfs2(r,r);
    cnt=0,build(1,n,rt=cnt++);
    for(ll i=1;i<=m;i++)
    {
        ll op,x,y,k;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            updates(x,y,k);
        }
        else if(op==2){
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",sum(x,y));
        }
        else if(op==3){
            scanf("%lld%lld",&x,&y);
            update(id[x],id[x]+size[x]-1,y,rt);
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",query(id[x],id[x]+size[x]-1,rt));
        }
    }
    return 0;
}

一个很不正经的后记

仔细看了大佬们的博客并很认真地整理出来，对树剖也有了更深的认识。
然后毛毛雨的第一篇博客大功告成啦！！
虽然格式排版暂时还莫得，但是毛毛雨后期会调的啦！！况且都这么晚了╭(╯^╰)╮
不如……晚安！(*๓´╰╯`๓)♡