danihao123's Blog

给你一棵\(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\)。

ETT野蛮，LCT文明，，，

换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点，每个实点（就是在树中真实存在的点）向他之前最晚建立的一个虚点认父。

然后虚点初始的时候应该向上一次的那个虚点认父（我们可以近似的认为第一个虚点就是1）。然后我们用类似于扫描线的做法，等到了虚点存在的区间里就把它爸爸改成相应的实点，出去了相应区间之后就再改回来。这样这题就很好做了，我们认为虚点点权为0，实点点权为1，然后查询就好做了。

然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理，因为同一个编号的结点一定分布编号连续的一段树里，所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。

再有一点就是查询的时候……如果直接查询两点间splay的和的话，可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离，再用LCA去掉不需要的。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
  Node *fa, *ch[2];
  int val, sumv;
  bool rev;
  int d() {
    return ((this == fa -> ch[1]) ? 1 : 0);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c;
    c -> fa = this;
  }
  void maintain() {
    sumv = ch[0] -> sumv + ch[1] -> sumv + val;
  }
  void paint() {
    rev = !rev;
    std::swap(ch[0], ch[1]);
  }
  void pushdown() {
    if(rev) {
      ch[0] -> paint();
      ch[1] -> paint();
      rev = false;
    }
  }
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
  nil = cur = pool;
  nil -> val = nil -> sumv = 0;
  nil -> rev = false;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
  x -> val = x -> sumv = val;
  x -> rev = false;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
  return x;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  Node *y = x -> fa; int d = x -> d();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  y -> sc(x -> ch[1 ^ d], d);
  x -> sc(y, 1 ^ d);
  y -> maintain(); x -> maintain();
}
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);
  }
  // x -> maintain();
}
Node *access(Node *x) {
  Node *nx = x, *y = nil;
  Node *ct = T(1);
  while(x != nil) {
    splay(x); x -> pushdown();
    if(x -> fa == nil) ct = x;
    x -> sc(y, 1); x -> maintain();
    y = x; x = x -> fa;
  }
  splay(nx); return ct;
}
Node *evert(Node *x) {
  access(x); x -> paint();
  return x;
}
void link(Node *x, Node *y) {
  evert(x); x -> fa = y;
}
void cut(Node *x) {
  access(x);
  x -> ch[0] -> fa = nil;
  x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
  evert(x); access(y);
  int d = x -> d();
  y -> ch[d] = nil; y -> maintain();
  x -> fa = nil;
}

int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
  if(a > x) {
    std::swap(a, x), std::swap(b, y);
  }
  if(b < x) return std::make_pair(n + 1, n + 1);
  if(b >= y) return std::make_pair(x, y);
  return std::make_pair(x, b);
}

int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
  freopen("forest1.in", "r", stdin);
  freopen("out", "w+", stdout);
#endif
  int m; scanf("%d%d", &n, &m);
  init_pool(); refresh(T(1), 1);
  int cnt0 = 1, cnt1 = 0, cnt2 = 0;
  Node *last1 = T(1);
  seg[1][0] = 1; seg[1][1] = n;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
    if(ope[i][0]) {
      scanf("%d", &ope[i][3]);
    }
    if(ope[i][0] == 0) {
      int c = ++ cnt0;
      refresh(T(c), 1);
      link(last1, T(c));
      seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
      printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
    } else if(ope[i][0] == 1) {
      Node *n1 = T(m + i);
      refresh(n1); link(n1, bef[i] = last1);
      int l = ope[i][1], r = ope[i][2], x = ope[i][3];
      auto s = seg_and(l, r, seg[x][0], seg[x][1]);
      l = s.first, r = s.second;
#ifdef LOCAL
      printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
      beg[l].push_back(i); end[r + 1].push_back(i);
      last1 = n1;
    } else {
      int x = ope[i][1], u = ope[i][2], v = ope[i][3];
      query[x].push_back(i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(auto id : end[i]) {
      Node *n1 = T(m + id);
      cut(n1, T(ope[id][3])); link(n1, bef[id]);
    }
    for(auto id : beg[i]) {
      Node *n1 = T(m + id);
      cut(n1, bef[id]); link(n1, T(ope[id][3]));
    }
    for(auto id : query[i]) {
      int u = ope[id][2], v = ope[id][3];
      evert(T(1)); access(T(u));
      int ret = T(u) -> sumv;
      Node *lca = access(T(v));
      ret += T(v) -> sumv;
      access(lca);
      ret -= lca -> sumv;
      ret -= lca -> sumv - 1;
      ans[id] = ret - 1;
    }
  }
  for(int i = 1; i <= m; i ++) {
    if(ope[i][0] == 2) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}