UOJ207 共价大爷游长沙

发表于

  题意: 一棵树，四个操作:

  1、删边 + 加边

  2、加入点对(x, y)

  3、删除第x个加入的点对

  4、询问当前所有点对之间的路径是否均经过边(x, y)

  这道题是动态树维护虚边信息的好题。
  考察操作4，所有点对路径均经过边(x, y)，就代表着将x作为树根后，所有点对均有且只有一个点在y的子树中。(包括y)
  我们将每一条路径随机一个很大的权值，并异或到对应点对的两个点上。则x作为根并access(y)后，y的实子树中只有点x。那么所有路径有且只有一个点在y子树中->y及其虚子树异或和=所有路径异或和。当然以上成立的条件是随机出的权值没有重复，异或和也不能有重复的。在int范围内随机就可以避免这个问题了。
  维护一个所有路径异或和now和每个节点的信息，加入与删除路径点对时记得在总异或和与路径两端点权值中加上(清掉)该路径权值，异或一下就好。
  这道题需要维护子树和，由于是第一次练习，为了写得更模板化，我多使用了几个变量:
  val —> 节点权值
  sum_chain —> 节点实子树权值和(包括节点本身)
  val_tree —> 节点虚子树权值和(不包括节点本身)
  sum_tree —> 节点及其实子树所有节点的虚子树权值和(不包括实子树节点及本身)
  以上所有权值和在本题中均指异或和。
  前两项是平时维护的东西，后面多出来的两项是额外维护的东西。
  这些东西可以干很多事情,比如: sum_tree + sum_chain = 该节点为根的子树的和
  又比如，将加法换成异或，则val ^ val_tree 就是我们要找的节点及虚子树的异或和。
  在题目中，有些东西可以合在一起维护，具体问题具体分析。
  维护虚边信息的动态树在写法上面有改变，尤其是node中的access操作。要留心。

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <ctime>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
#define getchar getchar_unlocked
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
	static char c; bool flag = 0;
	while(!isdigit(c = getchar())) if(c == '-') flag = 1;
	for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
	if(flag) x = -x; return x;
}
const int maxn = 100010, maxm = 300010;
struct node
{
	node *p, *c[2];
	bool rev;
	int val_tree, val;
	int sum_tree, sum_chain;
	node(): p(0), rev(0), val_tree(0), val(0), sum_tree(0), sum_chain(0) { ms(c, 0); }
	void setc(node* o, bool b) { c[b] = o; if(o) o->p = this; }
	
	bool isroot() { return !p || p->c[0] != this && p->c[1] != this; }
	bool getpos() { return p->c[1] == this; }
	void updrev() { rev ^= 1; }
	void pushup()
	{
		sum_tree = val_tree;
		sum_chain = val;
		rep(i, 0, 1) if(c[i])
		{
			sum_chain ^= c[i]->sum_chain;
			sum_tree ^= c[i]->sum_tree;
		}
	}
	void pushdown()
	{
		if(rev)
		{
			rep(i, 0, 1) if(c[i]) c[i]->updrev();
			swap(c[0], c[1]); rev = 0;
		}
	}
	void rot()
	{
		node *f = p; bool b = getpos();
		if(f->isroot()) p = f->p;
		else f->p->setc(this, f->getpos());
		f->setc(c[!b], b); setc(f, !b);
		f->pushup();
	}
	void relax() { if(!isroot()) p->relax(); pushdown(); }
	void splay()
	{
		for(relax(); !isroot(); rot())
			if(!p->isroot()) (p->getpos() == getpos() ? p : this)->rot();
		pushup();
	}
	void access()
	{
		for(node *u = this, *v = 0; u; v = u, u = u->p)
		{
			u->splay();
			if(u->c[1]) u->val_tree ^= u->c[1]->sum_tree ^ u->c[1]->sum_chain;
			if(v) u->val_tree ^= v->sum_tree ^ v->sum_chain;
			u->setc(v, 1), u->pushup();
		}
		splay();
	}
	void beroot() { access(); updrev(); }
}nd[maxn];
int n, m, now;
int a[maxm], cnt;
pair<int, int> path[maxm];
namespace LCT
{
	void link(int x, int y)
	{
		node *u = nd + x, *v = nd + y;
		u->beroot(); v->access();
		u->p = v; v->val_tree ^= u->sum_tree ^ u->sum_chain;
		v->pushup();
	}
	void cut(int x, int y)
	{
		node *u = nd + x, *v = nd + y;
		u->beroot(); v->access();
		u->p = v->c[0] = NULL;
		v->pushup();
	}
	void change(int x, int y)
	{
		node *u = nd + x;
		u->access(); u->val ^= y; u->pushup();
	}
	bool query(int x, int y)
	{
		node *u = nd + x, *v = nd + y;
		u->beroot(); v->access();
		return (v->val ^ v->val_tree) == now;
	}
}
using namespace LCT;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	srand(time(0)); scanf("%*d");
	read(n); read(m); int x, y;
	rep(i, 1, n - 1) read(x), read(y), link(x, y);
	while(m--)
	{
		int op; read(op);
		if(op == 1)
		{
			read(x); read(y); cut(x, y);
			read(x); read(y); link(x, y);
		}
		if(op == 2)
		{
			read(x); read(y);
			int Hash = rand();
			now ^= Hash;
			change(x, Hash); change(y, Hash);
			path[++cnt] = mp(x, y);
			a[cnt] = Hash;
		}
		if(op == 3)
		{
			read(x);
			change(path[x].first, a[x]);
			change(path[x].second, a[x]);
			now ^= a[x];
		}
		if(op == 4) read(x), read(y), puts(query(x, y) ? "YES" : "NO");
	}
	return 0;
}