Processing math: 100%

学习笔记·Link Cut Tree

发表于 |
字数统计: 776 | 阅读时长 ≈ 4

这一片文章我们来谈谈 LCT 在实际操作中的应用。

维护链上信息

一道模板题，会讲的比较详细。

考虑维护一个 valx 代表 x 所在 Splay 中 x 的子树异或和。

在查询 x 到 y 的点权和的时候，我们必须先 split(x,y)，也即将 x 到 y 的路径上的边全部抠出来扔到一个 Splay 上，再将 x 或者 y 旋转到这个 Splay 的根上，所以 valrt 就是答案了。

在修改 x 的点权的时候要先将 x 旋转到所在 Splay 的根上，就可以直接修改，否则就会比较麻烦。

还有一个点，注意到加边和删边操作不保证存在，因此要先判断一下再搞。

代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e5+51;
ll cnt,qcnt,op,x,y;
ll num[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
namespace LCT{
    struct Node{
        ll fa,val,rv;
        ll ch[2];
    };
    struct LinkCutTree{
        Node nd[MAXN];
    	ll st[MAXN];
		#define ls nd[x].ch[0]
		#define rs nd[x].ch[1]
    	inline bool nroot(ll x)
		{
			return nd[nd[x].fa].ch[0]==x||nd[nd[x].fa].ch[1]==x;
		}
    	inline void update(ll x)
		{
			nd[x].val=nd[ls].val^nd[rs].val^num[x];
		}
    	inline void reverse(ll x)
		{
			swap(ls,rs),nd[x].rv^=1;
		}
    	inline void spread(ll x)
	   	{
			if(nd[x].rv)
			{
				ls?reverse(ls):(void)1,rs?reverse(rs):(void)1;
				nd[x].rv=0;
			}
		}
    	inline void rotate(ll x)
		{
			ll fa=nd[x].fa,gfa=nd[fa].fa;
			ll dir=nd[fa].ch[1]==x,son=nd[x].ch[!dir];
			if(nroot(fa))
			{
				nd[gfa].ch[nd[gfa].ch[1]==fa]=x;
			}
			nd[x].ch[!dir]=fa,nd[fa].ch[dir]=son;
			if(son)
			{
				nd[son].fa=fa;
			}
			nd[fa].fa=x,nd[x].fa=gfa,update(fa);
		}
    	inline void splay(ll x)
		{
			ll fa=x,gfa,cur=0;
			st[++cur]=fa;
			while(nroot(fa))
			{
				st[++cur]=fa=nd[fa].fa;
			}
			while(cur)
			{
				spread(st[cur--]);
			}
			while(nroot(x))
			{
				fa=nd[x].fa,gfa=nd[fa].fa;
				if(nroot(fa))
				{
					rotate((nd[fa].ch[0]==x)^(nd[gfa].ch[0]==fa)?x:fa);
				}
				rotate(x);
			}
			update(x);
		}
    	inline void access(ll x)
		{
			for(register int i=0;x;x=nd[i=x].fa)
			{
				splay(x),rs=i,update(x);
			}
		}
    	inline void makeRoot(ll x)
		{
			access(x),splay(x),reverse(x);
		}
    	inline ll findRoot(ll x)
		{
			access(x),splay(x);
			while(nd[x].ch[0])
			{
				spread(x),x=ls;
			}
			return x;
		}
    	inline void split(ll x,ll y)
		{
			makeRoot(x),access(y),splay(y);
		}
    	inline void link(ll x,ll y)
		{
			makeRoot(x);
			if(findRoot(y)!=x)
			{
				nd[x].fa=y;
			}
		}
    	inline void cut(ll x,ll y)
		{
			makeRoot(x);
			if(findRoot(y)==x&&nd[x].fa==y&&!rs)
			{
				nd[x].fa=nd[y].ch[0]=0,update(y);
			}
		}
		#undef ls
		#undef rs
    };
}
LCT::LinkCutTree lct;
int main()
{
    cnt=read(),qcnt=read();
    for(register int i=1;i<=cnt;i++)
    {
        num[i]=read();
    }
    for(register int i=0;i<qcnt;i++)
    {
        op=read(),x=read(),y=read();
        if(!op)
        {
            lct.split(x,y);
            printf("%d\n",lct.nd[y].val);
        }
        if(op==1)
        {
            lct.link(x,y);
        }
        if(op==2)
        {
            lct.cut(x,y);
        }
        if(op==3)
        {
            lct.splay(x),num[x]=y;
        }
    }
}
Powered By Valine
v1.5.2