[UOJ207] 共价大爷游长沙

LCT维护子树信息好题(逃

题意

无根树,4种操作:

  • 加入一个点对
  • 删除一个点对
  • 删一条边并加一条边,使其仍然是一棵树
  • 查询一条边是否被所有点对间的路径所经过。

思路

首先考虑维护第四个询问。

一个点对的路径经过一条边等价于两个点分居与这条边两段。

我们可以考虑将两个端点都异或一个大随机数。这样只要这条边(较深的那一段)的子树异或和等于所有点值异或和就能保证这条边被所有路径经过。

然后就是要维护一个点的子树的异或和。

发现将这个点access()后它的子树就是所有虚边连的子树。

我们在更改虚边信息(access() link() cut())时维护子树异或和就可以了。

(震惊!ExtraTest竟卡随机数)

Code

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
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 300030;
int ss;
struct LinkCutTree
{
int fa[N],ch[N][2],sum[N],w[N],rev[N];
inline int dc(int k){return ch[fa[k]][1] == k;}
inline int isrt(int k){return ch[fa[k]][0] != k && ch[fa[k]][1] != k;}
inline void pu(int k){sum[k] = sum[ch[k][0]] ^ sum[ch[k][1]] ^ w[k];}
inline void rever(int k){rev[k] ^= 1;std::swap(ch[k][0],ch[k][1]);}
inline void pd(int k)
{
if(rev[k])
{
if(ch[k][0]) rever(ch[k][0]);
if(ch[k][1]) rever(ch[k][1]);
rev[k] = 0;
}
}
inline void rpd(int k){if(!isrt(k)) rpd(fa[k]);pd(k);}
inline void rot(int k)
{
int f = fa[k],ff = fa[f],d = dc(k);
fa[k] = ff;if(!isrt(f)) ch[ff][dc(f)] = k;
fa[ch[f][d] = ch[k][!d]] = f;
fa[ch[k][!d] = f] = k;
pu(f);pu(k);
}
inline void splay(int k)
{
rpd(k);
for(;!isrt(k);rot(k)) if(!isrt(fa[k])) rot(dc(fa[k]) == dc(k) ? fa[k] : k);
}
inline void access(int k)
{
for(int y = 0;k;y = k,k = fa[k])
{
splay(k);
w[k] ^= sum[ch[k][1]];
w[k] ^= sum[ch[k][1] = y];
pu(k);
}
}
inline void makert(int k){access(k);splay(k);rever(k);}
inline int findrt(int k)
{
access(k);splay(k);
while(ch[k][0]) pd(k),k = ch[k][0];
return k;
}
inline void split(int x,int y){makert(x);access(y);splay(y);}
inline void link(int x,int y)
{
makert(x);makert(y);
fa[x] = y;
w[y] ^= sum[x];pu(y);
}
inline void cut(int x,int y){split(x,y);if(fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0;pu(y);}
inline void modify(int x,int v){access(x);splay(x);w[x] ^= v;sum[x] ^= v;}
inline int query(int x,int y){makert(x);access(y);return w[y] == ss;}
}LCT;
struct edge{int u,v,w;}E[N];int tot = 0;
inline int rnd(){return ((rand() << 15) + rand());}
int main()
{
srand(time(NULL));
int id = getint(),n = getint(),m = getint();
for(int i = 1,u,v;i < n;i++) {u = getint(),v = getint();LCT.link(u,v);}
for(int i = 1,opt,x,y,z;i <= m;i++)
{
opt = getint();
if(opt == 1){LCT.cut(getint(),getint());LCT.link(getint(),getint());}
else if(opt == 2)
{
x = getint(),y = getint(),z = rnd();
E[++tot] = (edge){x,y,z};
LCT.modify(x,z);LCT.modify(y,z);
ss ^= z;
}
else if(opt == 3)
{
x = getint();
ss ^= E[x].w;
LCT.modify(E[x].u,E[x].w);LCT.modify(E[x].v,E[x].w);
}
else puts(LCT.query(getint(),getint()) ? "YES" : "NO");
}
return 0;
}