「UOJ #207」共价大爷游长沙 - LCT

给你一棵nn个点的树,需要支持4种操作:

  • 在路径集合中加入一条路径
  • 在路径集合中删除一条路径
  • 删一条边加一条边
  • 查询一条边是否被集合中所有路径经过

n100000,m300000n\le100000, m\le300000

UOJ207

Solution

这道题好巧妙啊

不难发现,如果某一条边(x,y)(x,y)要满足被集合中所有路径经过,就要满足以xx为根时,对于集合中每一条路经有且仅有一个端点在yy的子树中

于是可以给每条路径随机一个权值,每加入一条路径,就将两个端点的点权异或上这个权值

LCT维护子树权值异或和,每次询问对应子树内的权值异或和是否等于当前所有路径的权值异或和

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
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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Maxn = 1e5 + 100, Maxm = 3e5 + 100;

int N, M;
struct point { int x, y, z; } Point[Maxm];

namespace LCT
{
#define ls Tree[x].ch[0]
#define rs Tree[x].ch[1]
struct tree
{
int fa, ch[2], rev, val, sum, sum_v;
// sum维护的子树信息,sum_v维护的虚子树信息,val是本身权值
} Tree[Maxn];
int Stack[Maxn], top;

inline int is_root (int x) { return Tree[Tree[x].fa].ch[0] != x && Tree[Tree[x].fa].ch[1] != x; }
inline int judge (int x) { return Tree[Tree[x].fa].ch[1] == x; }
inline void push_up (int x) { Tree[x].sum = Tree[ls].sum ^ Tree[rs].sum ^ Tree[x].val ^ Tree[x].sum_v; }
inline void push_down (int x) { if (Tree[x].rev) swap(ls, rs), Tree[ls].rev ^= 1, Tree[rs].rev ^= 1, Tree[x].rev = 0; }
inline void connect (int x, int f, int dir) { Tree[x].fa = f, Tree[f].ch[dir] = x; }
inline void rotate (int x)
{
int f = Tree[x].fa, anc = Tree[f].fa, dirx = judge(x), dirf = judge(f);
if (!is_root(f)) Tree[anc].ch[dirf] = x; Tree[x].fa = anc;
connect (Tree[x].ch[dirx ^ 1], f, dirx);
connect (f, x, dirx ^ 1);
push_up (f), push_up(x);
}
inline void splay (int x)
{
Stack[++top] = x; for (int y = x; !is_root(y); y = Tree[y].fa) Stack[++top] = Tree[y].fa;
while (top) push_down (Stack[top--]);
for (; !is_root(x); rotate(x)) if (!is_root(Tree[x].fa)) rotate (judge(Tree[x].fa) == judge(x) ? Tree[x].fa : x);
}
inline void access (int x)
{
for (int y = 0; x; y = x, x = Tree[x].fa)
{
splay (x);
Tree[x].sum_v ^= Tree[y].sum, Tree[x].sum_v ^= Tree[rs].sum;
rs = y, push_up(x);
}
}
inline void make_root (int x) { access(x), splay(x), Tree[x].rev ^= 1; }
inline void split (int x, int y) { make_root(x), access(y), splay(y); }
inline void link (int x, int y) { make_root(x), make_root(y), Tree[x].fa = y, Tree[y].sum_v ^= Tree[x].sum; }
inline void cut (int x, int y) { split(x, y); Tree[x].fa = Tree[y].ch[0] = 0; push_up(y); }
inline int query (int x, int y) { split(x, y); return Tree[x].sum; }
inline void modify (int x, int val) { make_root(x), Tree[x].val ^= val, push_up(x); }
}

inline void Solve ()
{
for (int i = 1; i < N; ++i) LCT :: link (read<int>(), read<int>());
int sum_val = 0, point_cnt = 0;
while (M--)
{
int op = read<int>();
if (op == 1) LCT :: cut (read<int>(), read<int>()), LCT :: link (read<int>(), read<int>());
else if (op == 2)
{
int x = rand() % (int)(1e9) + 1;
Point[++point_cnt].x = read<int>(), Point[point_cnt].y = read<int>(), Point[point_cnt].z = x;
LCT :: modify (Point[point_cnt].x, x), LCT :: modify (Point[point_cnt].y, x);
sum_val ^= x;
}
else if (op == 3)
{
int id = read<int>();
LCT :: modify (Point[id].x, Point[id].z), LCT :: modify (Point[id].y, Point[id].z);
sum_val ^= Point[id].z;
}
else printf("%s\n", LCT :: query (read<int>(), read<int>()) == sum_val ? "YES" : "NO");
}
}

inline void Input ()
{
read<int>(), N = read<int>(), M = read<int>();
srand(N + M);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
Input();
Solve();
return 0;
}
感谢你的赞赏!