Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

动态树

Posted on Edited on

思想类似于树链剖分。

简介

  • 建立虚边和实边，动态在线查询两点间的路径

可实现的操作

  • $access(x)$：建立一条从 $x$ 到根节点的实边路径。
  • $make-root(x)$：将x变成根节点。
  • $find-root(x)$：找到 $x$ 所在树的根节点。
  • $splay(x, y)$：将 $x$ 到 $y$ 的路径变成实边路径。
  • $link(x, y)$：若 $x$ 和 $y$ 不连通的话，则加入$(x, y)$这条边。
  • $cut(x, y)$：若 $x$ 和 $y$ 之间有边的话就删掉这条边。
  • $isroot$：$x$ 是否是所在 $splay$ 的根节点。

具体实现

  • 用 $Splay$ 维护所有实边路径的中序遍历（本质上是维护实边），用 $splay$ 的后继前驱来维护原树的父子关系，其中虚边用 $splay$ 的根节点来维护
  • $access(x)$：首先将 $x$ 转到当前树的根节点去，再使x所在树的父亲节点y成为另一棵树的根节点，然后删去 $y$ 的右儿子，使 $y$ 的右儿子等于 $x$ （其中序遍历不变），然后不断的进行操作。
  • $make-root(x)$：同理先 $access(x)$再翻转 $x$ 所在的子树（原来 $x$ 在右下角，根在左下角，所以需要将 $x$ 转到左下角，使其成为根（一般还会将它转到最上面）。
  • $find-root$：一直向当前左子树走，直到走不动为止。
  • $splay(x, y)$：就是将 $x$ 转到 $y$ 的子树上，特别的 $splay(x, 0)$ 就是将 $x$ 转到根。
  • $link(x, y)$：$make-root(x)$，再$access(y)$。
  • $cut(x, y)$：先$make-root(x)$，再判断 $x$ 的右子树是不是 $y$，若不是，则 $x$ 和 $y$ 之间没有边，如果是，再判断 $y$ 有无左儿子，若有，则 $x$ 和 $y$ 之间没有边，否则断掉 $x$ 和 $y$ 的边，使 $x$ 的右儿子为 $y$ 的右儿子
  • $isroot$：找到 $x$ 的父节点 $y$，判断 $x$ 是否是 $y$ 的左右儿子，如果是，则 $x$ 不是根，否则 $x$ 就是根。

例题P3690 【模板】动态树（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
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
struct Node{
	int s[2], p, v;
	int sum, rev;
}tr[N];
int stk[N];
void pushrev(int x) // 翻转 
{
	swap(tr[x].s[0], tr[x].s[1]);
	tr[x].rev ^= 1;
}
void pushup(int x) 
{
	tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}
void pushdown(int x) // 下传懒标记 
{
	if(tr[x].rev)
	{
		pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
		tr[x].rev = 0;
	}
}
bool isroot(int x) //是否是当前splay的根 
{
	return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}
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 splay(int x) // 动态树是无根树，所以默认直接转到根 
{
	int top = 0, r = x;
	stk[++ top] = r;
	while(!isroot(r)) stk[++ top] = r = tr[r].p; //动态暴搜到根节点，stk存储 
	while(top) pushdown(stk[top --]);
	while(!isroot(x))
	{
		int y = tr[x].p, z = tr[y].p;
		if(!isroot(y))
		{
			if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x) // 建立一条x到根的路 
{
	int z = x;
	for(int y = 0; x; y = x, x = tr[x].p)
	{
		splay(x);
		tr[x].s[1] = y, pushup(x);
	}
	splay(z);
}
void make_root(int x)// 将x变为原树的根节点 
{
	access(x);
	pushrev(x);
}
int find_root(int x)//找到x所在的原树根节点，再将原树的根节点旋转到splay的根节点 
{
	access(x);
	while(tr[x].s[0]) pushdown(x), x = tr[x].s[0];
	splay(x);
	return x; 
}
void split(int x,int y)
{
	make_root(x);
	access(y);
}
void link(int x, int y)
{
	make_root(x);
	if(find_root(y) != x) tr[x].p = y;
}
void cut(int x, int y)
{
	make_root(x);
	if(find_root(y) == x && tr[y].p == x && !tr[y].s[0])
	{
		tr[x].s[1] = tr[y].p = 0;
		pushup(x);
	} 
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i ++) scanf("%d", &tr[i].v);
	while(m --)
	{
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if(t == 0)
		{
			split(x, y);
			printf("%d\n", tr[y].sum);
		}
		else if(t == 1) link(x, y);
		else if(t == 2) cut(x, y);
		else
		{
			splay(x);
			tr[x].v = y;
			pushup(x);
		}
	} 
	return 0;
}