mydcwfy's Blog

树链剖分

Posted on
Symbols count in article: 6.6k Reading time ≈ 14 mins.

可以将树上操作转化为区间操作。

树链剖分

1. 主要思想

通过给每一个节点一个重新的编号，使任意一条路径都变为不超过 $\log n$ 个连续区间。

于是，就可以将树上操作转化为区间操作。

并且是维护每一个点。

然后，一般使用线段树 or 树状数组实现。

2. 核心

一般来说，使用轻重链剖分。

将一个节点的儿子分为重儿子与轻儿子。

重儿子是指儿子所在子树最大的儿子，其余的为轻儿子。

如果有相同的话，任取一个即可。

重边就是指节点到重儿子的边。

重链是指极大的重边组成的路径。特别的，单个节点也可以做一条重链。

这样操作之后，每一个节点都在一条重链中。

我们在建立线段树时（即剖分时），要优先遍历重儿子。

这样就可以保证重链所在的线段树是连续的区间。

于是，任意一条路径都可以分为 $\log n$ 个区间。

这里先不证明了，可以自行理解。

3. 具体流程

1）预处理

首先遍历一遍，记录 size，并计算重儿子。

第二次，将树上节点按照重儿子优先的次序遍历，并转化到线段树上。

2）询问/更改

对于两个节点，如果他们不在同一重链，那么选择 $top$ 深度较大的点向上跳（即到 $x$ 到 $top$ 进行区间修改，在同一重链），直到在同一重链，直接区间修改。

如果还有不懂的，可以再看一下前面的解释结合后面的代码进行理解。

4. 例题

T1：树链剖分

题目传送门 Luogu

题目传送门 AcWing

模板题。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define l(p) (p<<1)
#define r(p) (p<<1|1)
using namespace std;

typedef long long ll;

const int N=1e5+10,M=2e5+10;

int h[N],e[M],ne[M],idx;
int sz[N],dep[N],son[N],f[N],top[N];
int id[N],nw[N],cnt,a[N];
int n,m;
bool vis[N];

struct Node{
    int l,r;
    ll lt,sum;
}tr[4*N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}

void dfs1(int x,int fa,int depth)
{
    f[x]=fa;
    vis[x]=1;sz[x]=1;dep[x]=depth; 
    for (int i=h[x];~i;i=ne[i])
        if (!vis[e[i]])
        {
            dfs1(e[i],x,depth+1);
            if (sz[e[i]]>sz[son[x]]) son[x]=e[i];
            sz[x]+=sz[e[i]];
        }
}

void dfs2(int x,int t)
{
    id[x]=++cnt,nw[cnt]=x,top[x]=t;
    if (!son[x]) return;
    dfs2(son[x],t);
    for (int i=h[x];~i;i=ne[i])
    {
        if (e[i]==f[x]||e[i]==son[x]) continue;
        dfs2(e[i],e[i]);
    }
}
//PreWork

void pushup(int p)
{
    tr[p].sum=tr[l(p)].sum+tr[r(p)].sum;
}

void pushdown(int p)
{
    if (tr[p].lt==0) return;
    Node &rt=tr[p],&le=tr[l(p)],&ri=tr[r(p)];
    le.sum+=(le.r-le.l+1)*rt.lt;le.lt+=rt.lt;
    ri.sum+=(ri.r-ri.l+1)*rt.lt;ri.lt+=rt.lt;
    rt.lt=0;
}

void build(int p,int l,int r)
{
    tr[p]=(Node){l,r};
    if (l==r)
    {
        tr[p].sum=a[nw[l]];
        return;
    }
    int mid=l+r>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
    pushup(p);
}

void modify(int p,int l,int r,ll x)
{
    if (tr[p].l>=l&&tr[p].r<=r)
    {
        tr[p].lt+=x;
        tr[p].sum+=x*(tr[p].r-tr[p].l+1);
        return;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if (l<=mid) modify(l(p),l,r,x);
    if (r>mid) modify(r(p),l,r,x);
    pushup(p);
}

ll query(int p,int l,int r)
{
    if (tr[p].l>=l&&tr[p].r<=r)
    {
        return tr[p].sum;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    ll ans=0;
    if (l<=mid) ans+=query(l(p),l,r);
    if (r>mid) ans+=query(r(p),l,r);
    return ans;
}
//SegmentTree

void update_path(int u,int v,ll x)
{
    while (top[u]!=top[v])
    {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,id[top[u]],id[u],x);
        u=f[top[u]];
    }
    modify(1,min(id[u],id[v]),max(id[u],id[v]),x);
}

void update_tree(int u,ll x)
{
    modify(1,id[u],id[u]+sz[u]-1,x);
}

ll query_path(int u,int v)
{
    ll ans=0;
    while (top[u]!=top[v])
    {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        ans+=query(1,id[top[u]],id[u]);
        u=f[top[u]];
    }
    ans+=query(1,min(id[u],id[v]),max(id[u],id[v]));
    return ans;
}

ll query_tree(int u)
{
    return query(1,id[u],id[u]+sz[u]-1);
}


int main()
{
    memset(h,-1,sizeof h);
    int r;
    ll p;
    scanf("%d %d %d %lld",&n,&m,&r,&p);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int i=1,a,b;i<n;++i)
    {
        scanf("%d %d",&a,&b);
        add(a,b);
    }
    dfs1(r,-1,1);
    dfs2(r,r);

    build(1,1,n);
    int op,u,v;
    ll k;
    while (m--)
    {
        scanf("%d %d",&op,&u);
        if (op==1)
        {
            scanf("%d %lld",&v,&k);
            update_path(u,v,k);
        }
        else if (op==3)
        {
            scanf("%lld",&k);
            update_tree(u,k);
        }
        else if (op==2)
        {
            scanf("%d",&v);
            printf("%lld\n",query_path(u,v)%p);
        }
        else if (op==4) printf("%lld\n",query_tree(u)%p);
    }
    return 0;
}

T2：[NOI2015]软件包管理器

题目传送门 Luogu

题目传送门 AcWing

首先，经过冗长的描述，我们可以知道该依赖关系构成一棵树。

当要卸载一个软件时，就是将该子树的所有节点状态改为 0。

如果要安装某个节点 x，等价于将根节点到 x 的路径上的节点状态改为 1。

输出就是所维护线段树的根节点的信息。

几乎就是模板题了。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define l(p) (p<<1)
#define r(p) (p<<1|1)
using namespace std;

const int N=1e5+10,M=2e5+10;

int h[N],e[M],ne[M],idx;
int sz[N],son[N],dep[N],f[N];
int id[N],nw[N],cnt,top[N];
int n,m;

struct Node{
    int l,r;
    int sum,flag;
    void init(int _l,int _r)
    {
        l=_l;r=_r;
        sum=0;flag=-1;
    }
}tr[4*N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs1(int x,int fa,int depth)
{
    f[x]=fa;dep[x]=depth;sz[x]=1;
    for (int i=h[x];~i;i=ne[i])
        if (e[i]!=fa)
        {
            dfs1(e[i],x,depth+1);
            if (sz[e[i]]>sz[son[x]]) son[x]=e[i];
            sz[x]+=sz[e[i]];
        }
}

void dfs2(int x,int t)
{
    id[x]=++cnt,nw[cnt]=x,top[x]=t;
    if (!son[x]) return;
    dfs2(son[x],t);

    for (int i=h[x];~i;i=ne[i])
    {
        if (e[i]==son[x]||e[i]==f[x]) continue;
        dfs2(e[i],e[i]);
    }
}
//Prework

void pushup(int p)
{
    tr[p].sum=tr[l(p)].sum+tr[r(p)].sum;
}

void pushdown(int p)
{
    if (~tr[p].flag)
    {
        Node &rt=tr[p],&le=tr[l(p)],&ri=tr[r(p)];
        le.flag=rt.flag,le.sum=(le.r-le.l+1)*rt.flag;
        ri.flag=rt.flag,ri.sum=(ri.r-ri.l+1)*rt.flag;
        rt.flag=-1;
    }
}

void build(int p,int l,int r)
{
    tr[p].init(l,r);
    if (l==r) return;
    int mid=l+r>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
}

void modify(int p,int l,int r,int x)
{
    if (tr[p].l>=l&&tr[p].r<=r)
    {
        tr[p].flag=x;
        tr[p].sum=x*(tr[p].r-tr[p].l+1);
        return;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if (l<=mid) modify(l(p),l,r,x);
    if (r>mid) modify(r(p),l,r,x);
    pushup(p);
}
//Segment Tree

void modify_path(int u,int v,int x)
{
    while (top[u]!=top[v])
    {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,id[top[u]],id[u],x);
        u=f[top[u]];
    }
    if (id[u]>id[v]) swap(u,v);
    modify(1,id[u],id[v],x);
}

int main()
{
    memset(h,-1,sizeof h);
    
    scanf("%d",&n);
    for (int i=2,f;i<=n;++i)
    {
        scanf("%d",&f);f++;
        add(f,i);
    }

    dfs1(1,-1,1);
    dfs2(1,1);
    build(1,1,n);

    scanf("%d",&m);
    char op[15];int x;
    while (m--)
    {
        scanf("%s%d",op,&x);x++;
        int last=tr[1].sum;
        if (op[0]=='u') modify(1,id[x],id[x]+sz[x]-1,0);
        else modify_path(1,x,1);
        printf("%d\n",abs(tr[1].sum-last));
    }
    return 0;
}