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]);

 }

巴特西

BZOJ 1969 航线规划 - LCT 维护边双联通分量

Solution

Code

最新文章

热门文章