mydcwfy's Blog

动态树

Posted on
Symbols count in article: 7.2k Reading time ≈ 16 mins.

比较难写，也比较难理解。

动态树

0. 前置知识

Splay

我的 Splay 文章

1. 主要思想与用途

用于处理树上的联通及统计问题。

时间复杂度为 $O(m\log n)$。

2. 主要思想

首先声明：祖先和儿子是人为定义的，其实是一棵无根树！

和树链剖分其实相似，我们也将树的边分为两种，为实边和虚边。

定义为每个点最多只有一条实边相连它的儿子，其他的我们称为虚边。

和重链类似，我们定义实边链为实边所连成的链。

但是，又和树链剖分不同，每一条链用 Splay 维护。所以树被拆成了若干个 Splay。单个点也可以有一个 Splay。

Splay 维护的就是从祖先到儿子的实边链，形状任意，用中序遍历维护。即我们如果中序遍历这一个 Splay，那么一定得到的是祖先到儿子的访问顺序。

但一般不称其为树套树（主要是太重要）。

回忆 Splay 的操作，我们发现：后继就是该点儿子，前驱就是该点父亲。

虚边不一定维护到真正的点，而是连到整个 Splay 的根节点来维护。具体的表现方式是指我们在儿子所在的 Splay 的根节点的父亲定义为这一个点。但是注意这个点的左右儿子都不是儿子所在 Splay 的根节点。

一定分清 Splay 的根节点和 Splay 深度最小的点！

将 Splay 的根节点连接至原树节点所代表的点。

下面有一个问题：

怎样区分实边和虚边？

仔细分析之后，我们发现，虚边只有儿子指向父亲，实边则还有父亲指向儿子。

所以，我们只要改变父亲所记录的儿子，就可以改变实边与虚边，而无需两边都进行维护。据此我们可以得出一个节点是不是所在 Splay 的根节点：直接判断它父亲有没有一个儿子是他自己。

画一个图。

它建出一堆 Splay 后（有些点没管）：

3. 主要操作

1）access

$\operatorname{access}(x)$ 是指将 x 到根节点的路径全部变为实边，把不合法的删去（因为可能有两个儿子的）。注意 $x$ 下面就没有实边了。

当遇到一个虚边时，假设我们当前的最高的点是 $y$，它的父亲是 $k$，我们将 $k$ 转到 Splay 的根，然后将 $k$ 的右儿子直接赋值为 $y$（可能原来也有值），但是我们要强制断掉，然后使得 $k-y$ 连上。

2）make_root

$\operatorname{make_root}(x)$ 是指将 x 变为整颗原树的根节点。

先调用 $\operatorname{access}(x)$，再直接转上去，调用 reverse。

将整个树看做是无根树，那么将 x 转到根节点，并打上 reverse 的 flag。

请注意，现在的拓扑序其实并没有变化，而且只是当前的顺序是变了一下，但是打了一个标记，其实后来走到的时候也要转回去。

3）find_root

$\operatorname{find_root}(x)$ 是指找到 x 所在树的深度最小的节点。

我们直接先 $\text{access}(x)$，然后一直向左儿子走。

4）split

$\operatorname{split}(x,y)$ 是指将 x 到 y 的路径建为实边。

先 $\operatorname{make_root}(x)$，再 $\operatorname{access}(y)$。

这里是指如果 x 和 y 不连通的话，就连起来。

将 x 转到根节点，判断 y 的根节点是不是 x 即可，如果不是，就直接连上即可。

6）cut

先将 x 转到整个树的根节点，再将 y 转至 x 的下面，最后判断 y 是不是 x 的后继。

注意我们前面说到 $y$ 下面没有实边。如果 x 为根，并且 $x-y$ 是 x 所在的 Splay 唯一的实边。如果是，直接删除。注意要双向删除，既不能作为一个简单的将实边变为虚边，而是儿子到父亲和父亲到儿子都要删。

7）isroot

判断 x 是否是所在 Splay 的根节点。前面已经讲到了。

以上就是 Link-Cut-Tree 的基本函数，也是核心函数。

非常绕，请务必理解并画图！

4. 代码

其实还算简单，但是细节不少，也有些难理解。

模板 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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;

struct Node{
    int s[2], fa;
    int val, rev;
}tr[N];
int n, m, a[N];

inline void pushup(int x)
{
    tr[x].val = tr[tr[x].s[0]].val ^ tr[tr[x].s[1]].val ^ a[x];
}

inline void reverse(int x)
{
    tr[x].rev ^= 1;
    swap(tr[x].s[0], tr[x].s[1]);
}

inline void pushdown(int x)
{
    if (!tr[x].rev) return;
    reverse(tr[x].s[0]), reverse(tr[x].s[1]);//注意 reverse 的方式
    tr[x].rev = 0;
}

bool isroot(int x){return x != tr[tr[x].fa].s[0] && x != tr[tr[x].fa].s[1];}

inline void rotate(int x)
{
    int y = tr[x].fa, z = tr[y].fa;
    int k = tr[y].s[1] == x;
    if (!isroot(y)) tr[z].s[y == tr[z].s[1]] = x;
    tr[x].fa = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].fa = y;
    tr[y].fa = x, tr[x].s[k ^ 1] = y;
    pushup(y), pushup(x);
}

inline void update(int x)
{
    if (!isroot(x)) update(tr[x].fa);
    pushdown(x);
}

inline void splay(int x)
{
    update(x);//先翻转回来
    while (!isroot(x))
    {
        int y = tr[x].fa, z = tr[y].fa;
        if (!isroot(y))
        {
            if ((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

void access(int x)
{
    int z = x;
    for (int y = 0; x; y = x, x = tr[y].fa)//最开始的 y 是 0，表示 x 开始没有向儿子的实边了
    {
        splay(x);
        tr[x].s[1] = y, pushup(x);//更改了信息就要 pushup
    }
    splay(z);
}

void makeroot(int x)
{
    access(x), reverse(x);
}

int findroot(int x)
{
    access(x);
    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];//注意要 pushup
    splay(x);
    return x;
}

void link(int x, int y)
{
    makeroot(x);
    if (findroot(y) != x) tr[x].fa = y;
}

void cut(int x, int y)
{
    makeroot(x);
    if (findroot(y) == x && tr[y].fa == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].fa = 0;
        pushup(x);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++ i) tr[i].val = a[i];
    int op, x, y;
    while (m --)
    {
        scanf("%d %d %d", &op, &x, &y);
        if (op == 0)
        {
            makeroot(x), access(y);
            printf("%d\n", tr[y].val);
        }
        else if (op == 1) link(x, y);
        else if (op == 2) cut(x, y);
        else if (op == 3){
            access(x);
            a[x] = y, pushup(x);
        }
    }
    return 0;
}

5. 例题

T1：魔法森林

题目传送门 Luogu

题目传送门 AcWing

看似是一个最短路，但是我们的最短路是处理单元的，并且两个没有联系，我们必须转换。

枚举 $a[i]$ 的取值，是 $\max(a[i])$ 答案为 $a[x]$，我们可以现在取不超过 $a[x]$ 的边，再求 $\max(b[i])$ 的值。

首先，我们考虑怎样维护整张图。

可以从小到大枚举 $a[i]$，使只加入边。

加入边，就是 Link-Cut-Tree 的模板。

但是，有一个问题：动态树只能维护树，而不能维护图，怎么办？

当加入一条边时，形成环时，我们去掉整个环的最大值，一定不会影响答案。

原因是如果取删掉的边，一定在删除这条边后可以找到比该解更优或者相同的解。

最后一个问题：怎样维护边上的权值？

我们可以使用 边化点 的技巧。

即在边中建一个点，使其的权值等于边的取值，即可。

（说实话很久前写的了，有些记不得了。而且码风还没改）

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define isroot(x) (tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x)
using namespace std;

const int N=1e5+5e4+10,INF=1e9;

int n,m,p[N];

struct Node{
    int s[2],p;
    int val,mx,flag;
    void init(int _p,int _val)
    {
        p=_p;val=_val;

    }
}tr[N];

struct Edge{
    int x,y,a,b;
    const bool operator <(const Edge &t) const{
        return a<t.a;
    }
}e[N];

void pushup(int x)
{
    tr[x].mx=x;
    for (int k=0;k<2;k++)
        if (tr[tr[tr[x].s[k]].mx].val>tr[tr[x].mx].val) tr[x].mx=tr[tr[x].s[k]].mx;
}

void reverse(int x)
{
    swap(tr[x].s[0],tr[x].s[1]);
    tr[x].flag^=1;
}

void pushdown(int x)
{
    if (!tr[x].flag) return;
    reverse(tr[x].s[0]);reverse(tr[x].s[1]);
    tr[x].flag=0;
}

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if (!isroot(y)) tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y);pushup(x);
}

void updata(int x)
{
    if (!isroot(x)) updata(tr[x].p);
    pushdown(x);
}

void splay(int x)
{
    updata(x);
    while (!isroot(x))
    {
        int y=tr[x].p,z=tr[y].p;
        if (!isroot(y))
            if ((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

void access(int x)
{
    int z=x;
    for (int y=0;x;y=x,x=tr[y].p)
    {
        splay(x);
        tr[x].s[1]=y;pushup(x);
    }
    splay(z);
}

void makeroot(int x)
{
    access(x);
    reverse(x);
}

int findroot(int x)
{
    access(x);
    while (tr[x].s[0]) pushdown(x),x=tr[x].s[0];
    splay(x);
    return x;
}

void split(int x,int y)
{
    makeroot(x);
    access(y);
}

void link(int x,int y)
{
    makeroot(x);
    if (findroot(y)!=x) tr[x].p=y;
}

void cut(int x,int y)
{
    split(x,y);
    if (findroot(y)==x&&tr[y].p==x&&!tr[y].s[1])
    {
        tr[y].p=tr[x].s[1]=0;
        pushup(x);
    }
}

int find(int x)
{
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1,x,y,a,b;i<=m;++i)
    {
        scanf("%d %d %d %d",&x,&y,&a,&b);
        e[i]=(Edge){x,y,a,b};
    }
    sort(e+1,e+m+1);
    for (int i=1;i<=n+m;++i)
    {
        p[i]=i;
        if (i>n) tr[i].val=e[i-n].b;
        tr[i].mx=i;
    }

    int res=INF;
    for (int i=1,x,y,t,a,b;i<=m;++i)
    {
        x=e[i].x,y=e[i].y,a=e[i].a,b=e[i].b;
        if (find(x)==find(y))
        {
            split(x,y);
            t=tr[y].mx;
            if (tr[t].val>b)
            {
                cut(e[t-n].x,t);cut(t,e[t-n].y);
                link(x,n+i);link(n+i,y);
            }
        }
        else
        {
            p[find(x)]=find(y);
            link(x,n+i),link(n+i,y);
        }
        
        
        if (find(1)==find(n))
        {
            split(1,n);
            res=min(res,a+tr[tr[n].mx].val);
        }
        // printf("%d\n",res);
    }
    if (res==INF) res=-1;
    printf("%d\n",res);
    return 0;
}