Solution
实际上就是查询 $u$ 到 $v$ 路径上 边双的个数 $ -1$。
并且题目仅有删边， 那么就离线倒序添边。
维护 边双 略有不同：
首先需要一个并查集， 记录 边双内的点。 在 添加边$(u,v)$时 ， 若$u, v$ 已经相连， 那么把 $u, v$ 路径上的点 缩成一个点， 用最上面的点 来代替。
void del(int x, int y) {
if (!x) return;
fa[x] = y;
del(lc(x), y);
del(rc(x), y);
}
压缩点
access 也应该变化 ： $f[x]$ 可能已经经过压缩了。
void access(int x) {
for (int y = ; x; y = x, x = f[y] = anc(f[x]))
splay(x), ch[x][] = y, up(x);
}
access
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std; const int N = 3e4 + ;
const int M = 1e5 + ; int n, m;
int fa[N], ans[N], vis[M]; struct edge {
int u, v; bool operator < (const edge &b) const {
return u == b.u ? v < b.v : u < b.u;
}
}e[M]; struct que {
int op, u, v;
}q[M]; int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} int anc(int x) {
return fa[x] == x? x : fa[x] = anc(fa[x]);
} namespace LCT {
int f[N], sz[N], ch[N][], tun[N];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1] int isroot(int x) {
return rc(f[x]) != x && lc(f[x]) != x;
} int get(int x) {
return rc(f[x]) == x;
} void rev(int x) {
swap(lc(x), rc(x));
tun[x] ^= ;
} void up(int x) {
sz[x] = ;
if (lc(x)) sz[x] += sz[lc(x)];
if (rc(x)) sz[x] += sz[rc(x)];
} void pushdown(int x) {
if (tun[x]) {
if (lc(x)) rev(lc(x));
if (rc(x)) rev(rc(x));
tun[x] = ;
}
} void pd(int x) {
if (!isroot(x))
pd(f[x]);
pushdown(x);
} void rotate(int x) {
int old = f[x], oldf = f[old], son = ch[x][get(x) ^ ];
if (!isroot(old)) ch[oldf][get(old)] = x;
ch[x][get(x) ^ ] = old;
ch[old][get(x)] = son;
f[son] = old; f[x] = oldf; f[old] = x;
up(old); up(x);
} void splay(int x) {
pd(x);
for (; !isroot(x); rotate(x))
if (!isroot(f[x]))
rotate(get(f[x]) == get(x) ? f[x] : x);
} void access(int x) {
for (int y = ; x; y = x, x = f[y] = anc(f[x]))
splay(x), ch[x][] = y, up(x);
} int findr(int x) {
access(x); splay(x);
while (lc(x)) pushdown(x), x = lc(x);
return x;
} void mroot(int x) {
access(x); splay(x); rev(x);
} void split(int x, int y) {
mroot(x); access(y); splay(y);
} void del(int x, int y) {
if (!x) return;
fa[x] = y;
del(lc(x), y);
del(rc(x), y);
} void link(int x, int y) {
mroot(x);
f[x] = y;
} void merge(int x, int y) {
x = anc(x); y = anc(y);
if (x == y)
return;
mroot(x);
if (findr(y) != x)
link(x, y);
else {
splay(x);
del(rc(x), x);
rc(x) = ; up(x);
}
}
} using namespace LCT; int main()
{
n = rd; m = rd;
for (int i = ; i <= n; ++i)
fa[i] = i;
for (int i = ; i <= m; ++i) {
e[i].u = rd; e[i].v = rd;
if (e[i].u > e[i].v)
swap(e[i].u, e[i].v);
}
sort(e + , e + + m);
int Q = ;
for (; ; ) {
int op = rd;
if (op == -)
break;
int u = rd, v = rd;
if (u > v)
swap(u, v);
q[++Q].op = op; q[Q].u = u;
q[Q].v = v;
edge t;
t.u = u; t.v = v;
if (op == )
vis[lower_bound(e + , e + + m, t) - e] = ;
}
for (int i = ; i <= m; ++i)
if (!vis[i])
merge(e[i].u, e[i].v);
for (int i = Q; i; i--) {
if (q[i].op == ) {
int x = q[i].u, y = q[i].v;
x = anc(x); y = anc(y);
if (x == y) {ans[i] = ; continue;}
split(x, y);
ans[i] = sz[y] - ;
}
else merge(q[i].u, q[i].v);
}
for (int i = ; i <= Q; ++i)
if (q[i].op == )
printf("%d\n", ans[i]);
}