NC203501. 市政交通
描述
输入描述
输入的第一行包含两个整数 n, m。接下来 n-1 行，每行两个整数 u, v，代表这两个点之间有一条边。接下来 m 行，每行描述一个操作。每行的第一个数为op:如果 op = 1 ,接下来输入两个数x , y，表示从 x 到 y 的公交线路开通了，保证之前没有相同的线路。
如果 op = 2 ,接下来输入两个数x , y，表示从 x 到 y 的公交线路被取消了。如果 op = 3 ,接下来输入两个数u , v, x, y，表示从 u 到 v 的边断开了，从 x 到 y 的边出现了。如果 op = 4 ,接下来输入两个数u , v，表示询问从 u 到 v 的边对应的答案，你应当输出询问结果。
输出描述
对于每一个 op = 4 的操作，你需要输出一个数 -1 或两个数，需为当前存在的一条公交线路。
示例1
输入:
5 6 1 2 2 3 3 4 3 5 1 4 5 4 2 3 3 3 5 1 5 4 2 3 2 4 5 4 1 2
输出:
-1 4 5 -1
C++11(clang++ 3.9) 解法, 执行用时: 3847ms, 内存消耗: 128368K, 提交时间: 2020-03-20 22:49:28
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define BSZ 3000
mt19937_64 rng(1926);
const int N = 100010;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
struct LinkCut2{
#define lrson(x) (x == ch[fa[x]][1])
#define isroot(x) (x!=ch[fa[x]][0] && x!=ch[fa[x]][1])
int rev[N],ch[N][2],fa[N];
bitset<BSZ> val[N],rval[N] = {0},xval[N] = {0};
void PullUp(int x){val[x] = val[ch[x][0]]^val[ch[x][1]]^rval[x]^xval[x];}
void PushDown(int x){
if(rev[x]){
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;
rev[x] = 0;
}
}
void Update(int x){
if(!isroot(x)) Update(fa[x]);
PushDown(x);
}
void Rotate(int x){
int cf = fa[x],lr = lrson(x);
if(!isroot(cf)) ch[fa[cf]][lrson(cf)] = x;
fa[x] = fa[cf]; fa[cf] = x;
fa[ch[x][lr^1]] = cf;
ch[cf][lr] = ch[x][lr^1];
ch[x][lr^1] = cf;
PullUp(cf);PullUp(x);
}
void Splay(int x){
Update(x);
while(!isroot(x)){
int y = fa[x],z = fa[y];
if(isroot(y)) Rotate(x);
else{
Rotate((lrson(z) == lrson(y))?y:x);
Rotate(x);
}
}
}
void Access(int x){
int cf = x;x = 0;
while(cf){
Splay(cf);
xval[cf]^=val[ch[cf][1]]^val[x];
ch[cf][1] = x;
PullUp(cf);
x = cf;
cf = fa[x];
}
}
inline void makeRoot(int x) {
Access(x); Splay(x);
rev[x] ^= 1;
}
void Link(int u,int v){
makeRoot(u);
makeRoot(v);
fa[u] = v;
xval[v]^=val[u];
val[v]^=val[u];
}
void Cut(int u,int v){
makeRoot(u);
Access(v); Splay(u);
ch[u][1] = 0;
PullUp(u);
fa[v] = 0;
}
int Find(int u){
Access(u);Splay(u);
int p = u;
while(1){
PushDown(p);
if(!ch[p][0])break;
p = ch[p][0];
}
Splay(p);
return p;
}
void upd(int u,int a1,int a2,int a3){
makeRoot(u);
rval[u].flip(a1);
rval[u].flip(a2);
rval[u].flip(a3);
val[u].flip(a1);
val[u].flip(a2);
val[u].flip(a3);
}
#undef lrson
#undef isroot
} LCT2;
struct LinkCut{
#define lrson(x) (x == ch[fa[x]][1])
#define isroot(x) (x!=ch[fa[x]][0] && x!=ch[fa[x]][1])
int rev[N],ch[N][2],fa[N],sz[N];
void PullUp(int x){
sz[x] = sz[ch[x][0]]+sz[ch[x][1]]+1;
}
void PushDown(int x){
if(rev[x]){
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;
rev[x] = 0;
}
}
void Update(int x){
if(!isroot(x)) Update(fa[x]);
PushDown(x);
}
void Rotate(int x){
int cf = fa[x],lr = lrson(x);
if(!isroot(cf)) ch[fa[cf]][lrson(cf)] = x;
fa[x] = fa[cf]; fa[cf] = x;
fa[ch[x][lr^1]] = cf;
ch[cf][lr] = ch[x][lr^1];
ch[x][lr^1] = cf;
PullUp(cf);PullUp(x);
}
void Splay(int x){
Update(x);
while(!isroot(x)){
int y = fa[x],z = fa[y];
if(isroot(y)) Rotate(x);
else{
Rotate((lrson(z) == lrson(y))?y:x);
Rotate(x);
}
}
}
void Access(int x){
int cf = x;x = 0;
while(cf){
Splay(cf);
ch[cf][1] = x;
PullUp(cf);
x = cf;
cf = fa[x];
}
}
inline void makeRoot(int x) {
Access(x); Splay(x);
rev[x] ^= 1;
}
void Link(int u,int v){
makeRoot(u);
fa[u] = v;
}
void Cut(int u,int v){
makeRoot(u);
Access(v); Splay(u);
ch[u][1] = 0;
PullUp(u);
fa[v] = 0;
}
int Find(int u){
Access(u);Splay(u);
int p = u;
while(1){
PushDown(p);
if(!ch[p][0])break;
p = ch[p][0];
}
Splay(p);
return p;
}
#undef lrson
#undef isroot
} LCT;
int n,m,u,v,x,y;
map<pii,ull> Mp;
set<pii> Query[BSZ];
int main() {
read(n,m);
for(int i=1;i<=n;i++){
LCT2.rval[i] = 0;
LCT2.PullUp(i);
}
for(int i=1;i<n;i++){
read(u,v);
LCT2.Link(u,v);
LCT.Link(u,v);
}
int op,id;
for(int i=0;i<m;i++){
read(op);
if(op == 1){
read(u,v);
ull chsh = rng();
Mp[mp(u,v)] = chsh;
int a = chsh%BSZ,b = (chsh/BSZ)%BSZ,c = (chsh/BSZ/BSZ)%BSZ;
if(b == a)b = (b+1)%BSZ;if(c == a)c = (c+2)%BSZ;if(c == b)c = (c+1)%BSZ;
Query[a].insert(mp(u,v));
Query[b].insert(mp(u,v));
Query[c].insert(mp(u,v));
LCT2.upd(u,a,b,c);
LCT2.upd(v,a,b,c);
}
if(op == 2){
read(u,v);
ull chsh = Mp[mp(u,v)];
int a = chsh%BSZ,b = (chsh/BSZ)%BSZ,c = (chsh/BSZ/BSZ)%BSZ;
if(b == a)b = (b+1)%BSZ;if(c == a)c = (c+2)%BSZ;if(c == b)c = (c+1)%BSZ;
LCT2.upd(u,a,b,c);
LCT2.upd(v,a,b,c);
Mp.erase(mp(u,v));
Query[a].erase(mp(u,v));
Query[b].erase(mp(u,v));
Query[c].erase(mp(u,v));
}
if(op == 3){
read(u,v,x,y);
LCT2.Cut(u,v);
LCT2.Link(x,y);
LCT.Cut(u,v);
LCT.Link(x,y);
}
if(op == 4){
read(u,v);
LCT2.Cut(u,v);
LCT2.makeRoot(v);
LCT.Cut(u,v);
int cp = LCT2.val[v]._Find_first();
if(cp == BSZ){
puts("-1");
}else{
for(auto ech:Query[cp])
if(LCT.Find(ech.first)!=LCT.Find(ech.second)){
printf("%d %d\n",ech.first,ech.second);
break;
}
}
LCT.Link(u,v);
LCT2.Link(u,v);
}
}
return 0;
}