给你一棵\(n\)个点的树，要求你滋磁以下操作（共\(m\)次）：

• 对于给定的点对\((x, y)\)和\((u, v)\)，删除边\((x, y)\)，添加边\((u, v)\)。保证操作时\((u, v)\)存在，并且保证操作后的图还是一棵树。
• 向集合\(S\)中加入一个点对\((u, v)\)。
• 从\(S\)中删除一个点对。
• 给定一条边\((x, y)\)（保证在当前树中存在），求问是否所有\((u, v)\in S\)都满足\(u\)到\(v\)的路径经过了\((x, y)\)。

\(1\leq n\leq 10^5, 1\leq m\leq 300000\)。

我们先想下如果没有link和cut操作的话怎么做……做法倒也很简单，树剖之后统计每条边被多少点对经过过，然后就随便做力……

不过这个做法放到LCT上是不行的……我们考虑用随机权值，给所有点对（其实就相当于非树边？）赋一个随机权值，然后这个点对对应的路径上的所有树边都要异或上这个权值。那么如果一条边的权值为当前所有点对权值的异或和的话那么就是被所有点对经过了的。

然后我们考虑link和cut的时候怎么维护……我们假设是先link再cut，那么显然会形成一个环。注意所有覆盖了\((x, y)\)（即要被cut的边）在cut之后都会走环的另一侧（相对于\((x, y)\)），而\((x, y)\)所在一侧就不会走了，所以我们直接将\(x\)到\(y\)路径上每条边都异或上原来\((x, y)\)的权值即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cctype>
#include <ctime>
#include <algorithm>
#include <functional>
#include <utility>
#include <random>
#include <map>
const int bufsiz = 128 * 1024 * 1024;
char buf[bufsiz]; char *cur = buf;
void *alloc(size_t size) {
  if(cur - buf + size > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

using ull = unsigned long long;
struct Node {
  Node *ch[2], *fa;
  ull val, lz; bool flag;
  int d() {
    return (fa -> ch[1] == this);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c; c -> fa = this;
  }
  void paint(ull v) {
    val ^= v; lz ^= v;
  }
  void paint() {
    flag ^= 1; std::swap(ch[0], ch[1]);
  }
  void pushdown() {
    if(flag) {
      ch[0] -> paint();
      ch[1] -> paint();
      flag = false;
    }
    if(lz != 0ULL) {
#ifdef LOCAL
      printf("Pushing down %llu!\n", lz);
#endif
      ch[0] -> paint(lz);
      ch[1] -> paint(lz);
      lz = 0;
    }
  }
};
Node *nil;
void init_pool() {
  nil = (Node*)alloc(sizeof(Node));
  nil -> ch[0] = nil -> ch[1] = nil; nil -> fa = nil;
  nil -> lz = nil -> val = 0; nil -> flag = false;
}
Node *alloc_node() {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> ch[0] = ret -> ch[1] = ret -> fa = nil;
  ret -> lz = ret -> val = 0; ret -> flag = false;
  return ret;
}

bool is_root(Node *o) {
  return (o -> fa == nil || (o -> fa -> ch[0] != o && o -> fa -> ch[1] != o));
}
void zig(Node *x) {
  int d = x -> d(); Node *y = x -> fa;
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  y -> sc(x -> ch[d ^ 1], d);
  x -> sc(y, d ^ 1);
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) y -> fa -> pushdown();
    y -> pushdown(); x -> pushdown();
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
}
void access(Node *x) {
  Node *vx = x, *y = nil;
  while(x != nil) {
    splay(x); x -> pushdown();
    x -> sc(y, 1);
    y = x; x = x -> fa;
  }
  splay(vx);
}
void evert(Node *x) {
  access(x); x -> paint();
}
void link(Node *x, Node *y) {
  evert(x); x -> fa = y;
}
void cut(Node *x, Node *y) {
  evert(x); access(y);
  int d = x -> d();
  y -> ch[d] = nil; x -> fa = nil;
}

const int maxn = 400005;
Node *T[maxn]; int n, m;
using pii = std::pair<int, int>;
ull val[maxn]; pii road[maxn];
int main() {
  init_pool();
  int task_id; scanf("%d", &task_id);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    T[i] = alloc_node();
  }
  
  std::map<pii, Node*> E;
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    if(u > v) std::swap(u, v);
    Node *th = alloc_node();
    E[{u, v}] = th;
    link(T[u], th); link(T[v], th);
  }
  std::mt19937_64 gen(time(0)); int rc = 0; ull all = 0;
  while(m --) {
    int op; scanf("%d", &op);
    if(op == 1) {
      int x, y, u, v; scanf("%d%d%d%d", &x, &y, &u, &v);
      if(x > y) std::swap(x, y);
      if(u > v) std::swap(u, v);
      Node *desu = E[{x, y}]; E.erase({x, y});
      access(desu);
      ull p = desu -> val; cut(desu, T[x]); cut(desu, T[y]);
#ifdef LOCAL
      printf("Deleting edge (%d, %d, %llu)\n", x, y, p);
#endif
      Node *ne = alloc_node(); E[{u, v}] = ne;
      link(T[u], ne); link(T[v], ne);
      evert(T[x]); access(T[y]); T[y] -> paint(p);
    } else if(op == 2) {
      rc ++;
      int x, y; scanf("%d%d", &x, &y);
      if(x > y) std::swap(x, y);
      road[rc] = pii(x, y); val[rc] = gen(); all ^= val[rc];
#ifdef LOCAL
      printf("val[%d] : %llu\n", rc, val[rc]);
#endif
      evert(T[x]); access(T[y]); T[y] -> paint(val[rc]);
    } else if(op == 3) {
      int x; scanf("%d", &x);
      int u = road[x].first, v = road[x].second;
      evert(T[u]); access(T[v]); T[v] -> paint(val[x]);
      all ^= val[x];
    } else {
      int x, y; scanf("%d%d", &x, &y);
      if(x > y) std::swap(x, y);
      Node *th = E[{x, y}]; access(th);
#ifdef LOCAL
      printf("all value : %llu\n", all);
      printf("this value : %llu\n", th -> val);
#endif
      if(th -> val == all) {
        puts("YES");
      } else {
        puts("NO");
      }
    }
  }
  return 0;
}

• 相关文章
• 全局相关文章