目录

  1. 引言
  2. UOJ #207. 共价大爷游长沙
    1. 输入格式
    2. 输出格式
    3. 样例一
      1. input
      2. output
    4. explanation
    5. 样例二
    6. 样例三
    7. 限制与约定
    8. 来源
    9. 题解
    10. 下载
    11. 题目分析
    12. 代码

引言

UOJ #207. 共价大爷游长沙 题解

UOJ #207. 共价大爷游长沙

火车司机出秦川,跳蚤国王下江南,共价大爷游长沙。每个周末,勤劳的共价大爷都会开车游历长沙市。

长沙市的交通线路可以抽象成为一个 $n$ 个点 $n-1$ 条边的无向图,点编号为 $1$ 到 $n$,任意两点间均存在恰好一条路径,显然两个点之间最多也只会有一条边相连。有一个包含一些点对 $(x,y)$ 的可重集合S,共价大爷的旅行路线是这样确定的:每次他会选择 $S$ 中的某一对点 $(x,y)$,并从 $x$ 出发沿着唯一路径到达 $y$。

小L是共价大爷的脑残粉,为了见到共价大爷的尊容,小L决定守在这张图的某条边上等待共价大爷的到来。为了保证一定能见到他,显然小L必须选择共价大爷一定会经过的边——也就是所有共价大爷可能选择的路径都经过的边。

现在小L想知道,如果他守在某一条边,是否一定能见到共价大爷。

然而长沙市总是不断的施工,也就是说,可能某个时刻某条边会断开,同时这个时刻一定也有某条新边会出现,且任意时刻图都满足任意两点间均存在恰好一条路径的条件。注意断开的边有可能和加入的新边连接着相同的两个端点。共价大爷的兴趣也会不断变化,所以S也会不断加入新点对或者删除原有的点对。当然,小L也有可能在任何时候向你提出守在某一条边是否一定能见到共价大爷的问题。你能回答小L的所有问题吗?

输入格式

输入的第一行包含一个整数 $\mathrm{id}$,表示测试数据编号,如第一组数据的$\mathrm{id} = 1$,样例数据的 $\mathrm{id}$ 可以忽略。hack数据中的 $\mathrm{id}$必须为 $0$ 到 $10$ 之间的整数。hack数据中$\mathrm{id}$的值和数据类型没有任何关系。

输入的第二行包含两个整数 $n, m$,分别表示图中的点数,以及接下来会发生的事件数,事件的定义下文中会有描述。初始时 $S$ 为空。

接下来 $n - 1$ 行,每行两个正整数 $x, y$,表示点 $x$ 和点 $y$ 之间有一条无向边。

接下来 $m$ 行,每行描述一个事件,每行的第一个数 $\mathrm{type}$ 表示事件的类型。

若$\mathrm{type} = 1$,那么接下来有四个正整数$x, y, u, v$,表示先删除连接点$x$和点$y$的无向边,保证存在这样的无向边,然后加入一条连接点$u$和点$v$的无向边,保证操作后的图仍然满足题中所述条件。

若$\mathrm{type} = 2$,那么接下来有两个正整数 $x, y$,表示在 $S$ 中加入点对 $(x, y)$。

若$\mathrm{type} = 3$,那么接下来有一个正整数 $x$,表示删除第 $x$ 个加入 $S$ 中的点对,即在第 $x$ 个 $\mathrm{type} = 2$ 的事件中加入 $S$ 中的点对,保证这个点对存在且仍然在 $S$ 中。

若 $\mathrm{type} = 4$,那么接下来有两个正整数 $x, y$,表示小L询问守在连接点 $x$ 和点 $y$ 的边上是否一定能见到共价大爷,保证存在这样的无向边且此时 $S$ 不为空。

输出格式

对于每个小L的询问,输出“YES”或者“NO”(均不含引号)表示小L一定能或者不一定能见到共价大爷。

样例一

input

0
5 7
1 2
1 3
2 4
1 5
2 1 5
1 1 5 2 5
4 2 5
2 1 4
4 2 5
3 1
4 2 4

output

YES
NO
YES

explanation

最开始将点对 $(1,5)$ 加入到 $S$ 中,此时点 $1$ 和点 $5$ 之间的路径是 $1 \rightarrow 5$。

接着将连接点 $1$ 和点 $5$ 的边断开,加入连接点 $2$ 和点 $5$ 的边,我们发现图仍然满足题中所述条件,且点 $1$ 和点 $5$ 之间的路径是 $1 \rightarrow 2 \rightarrow 5$,经过点了 $2$ 和点 $5$ 之间的边,因此第一个询问答案是 YES

接着将点对 $(1,4)$ 加入到 $S$ 中,点 $1$ 和点 $4$ 之间的路径是 $1 \rightarrow 2 \rightarrow 4$,没有经过点 $2$ 和点 $5$ 之间的边,因此第二个询问答案是 NO

接着,我们删除了第一个加入到 $S$ 中的点对,也就是点对 $(1,5)$,此时 $S$ 中唯一的点对就是 $(1,4)$,经过了点 $2$ 和点 $4$ 之间的边,因此最后一个询问答案是 YES

样例二

见样例数据下载。

样例三

见样例数据下载。这组数据中 $\mathrm{type} \ne 1$。

限制与约定

每组测试数据的限制与约定如下所示:

测试点编号 $n$ $m$ $\mathrm{type}=$ 限制与约定
1$n \le 100$$m \le 100$$1,2,3,4$
2$n \le 100000$$m \le 300000$$2,4$
3
4$2,3,4$
5
6$1,2,3,4$任意时刻 $|S| \le 10$
7
8
9
10

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

来源

matthew99

题解

http://matthew99.blog.uoj.ac/blog/1771

下载

样例数据下载

题目分析

这道题,我们发现,由于新增了一个集合,我们很难快速的应对整个集合的批量信息维护要求,因为集合内部有增删操作,外部也有树的形态改变,如果直接维护所有点对形成的链的交,外部形态改变可能会影响到所有的集合内的元素,所以这样就十分地差

我们发现,主要问题是维护链交很难同时维护所有集合内的点对的有关信息,因此我们现在想要做的,就是用一种方法快速地包含集合内的信息,同时在外部形态改变的时候不会受到太大影响(最好是无影响),能够快速反映这种变化

我们知道,如果一条边满足题目的条件,那么我们可以发现,这条边两端的每个子树中,一定包含每个点对中的恰好一个点,其他的情况都不成立

只包含一次的时候才计算,二次或是不出现都不计算,这让我们想到什么?没错,那就是异或运算!

进一步,由于我们要快速包含所有信息,而异或也正可以尽可能多地包含所有的原有信息,并且运算方便快捷

通过异或,我们可以联想异或的有关应用,我们常常使用异或值的相等关系来进行等价性判定,这就是Hash的思想

我们知道,在字符串中,我们有一种方法叫做Hash,我们在改变字符串的时候,Hash很容易维护,而用Hash来进行相等判断,只需要$O(1)$的时间,我们可以考虑这样做

我们为每一个点对随意赋上一个权值,然后,我们维护每个点里面的所有点的权值的子树异或和,使用经典的LCT维护子树方法即可做到这一点

在判定时,我们维护一个当前集合内所有点对的异或和,然后直接比较这条边的某一个端点的子树异或和是否与之相等即可

注意,随机权值在int范围内时会被hack,需要增大随机范围到long long int方可通过本题

代码

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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
//#define DEBUG
#define maxn 200005
#define INF 2000000005
#define ls ch[x][0]
#define rs ch[x][1]
#define ll long long int
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
ll all = 0;
ll val[maxn];
ll sum[maxn];
ll vsum[maxn];
int fa[maxn];
int ch[maxn][2];
bool rev[maxn];
inline bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
sum[x] = vsum[x] ^ sum[ls] ^ sum[rs] ^ val[x];
}
inline void pushv(int x){
vsum[fa[x]] ^= sum[x];
}
inline void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
swap(ls, rs);
rev[x] = 0;
}
}
inline void rotate(int x){
int k = x;
x = fa[x];
if (!x) return;
fa[k] = fa[x];
int d = ch[x][1] == k;
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
int st[maxn];
int cst = 0;
void splay(int x){
if (!x) assert(false);
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if (!x) assert(false);
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
if (!x) assert(false);
rotate(x);
}
}
void access(int x){
int t = 0;
while (x){
splay(x);
pushv(rs), pushv(t);
rs = t;
pushup(x);
t = x;
x = fa[x];
}
}
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void split(int x, int y){
moveroot(y);
access(x);
splay(x);
}
void cut(int x, int y){
split(x, y);
ls = fa[y] = 0;
pushup(x);
}
void link(int x, int y){
moveroot(y);
moveroot(x);
fa[x] = y;
pushv(x);
}
void modify(int x, ll y){
access(x), splay(x);
val[x] ^= y;
}
void get(int x, int y){
moveroot(y);
access(x);
int f1 = ((vsum[x] ^ val[x]) == all);
moveroot(x);
access(y);
int f2 = ((vsum[y] ^ val[y]) == all);
if (f1 ^ f2) assert(false);
if (f1) printf("YES\n");
else printf("NO\n");
}
struct ele{
int x, y;
ll z;
ele(int x = 0, int y = 9, ll z = 0) : x(x), y(y), z(z){}
}save[maxn];
int cnt = 0;
int main(){
#ifndef ONLINE_JUDGE
freopen("changsha.in", "r", stdin);
#endif
int x, y, op;
ll z;
read(n);
read(n), read(m);
rep(i, 1, n - 1) read(x), read(y), link(x, y);
rep(i, 1, m){
read(op);
switch(op){
case 1: read(x), read(y), cut(x, y), read(x), read(y), link(x, y); break;
case 2: read(x), read(y); z = (ll)rand() * rand(); modify(x, z), modify(y, z), save[++cnt] = ele(x, y, z), all ^= z; break;
case 3: read(x), modify(save[x].x, save[x].z), modify(save[x].y, save[x].z), all ^= save[x].z; break;
case 4: read(x), read(y), get(x, y); break;
}
}
return 0;
}