[BZOJ4530] [BJOI 2014] 대융합.

[제목 링크]

클릭하여 링크 열기

[발상 요점]

LinkCutTree로 이 나무를 유지하고 가벼운 아버지에게 자수 정보를 기록하면 된다.

시간 복잡도 O(QLogN) O(Q L o g N).

【코드】

#include

using namespace std;
const int MAXN = 100005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
  x = 0; int f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  x *= f;
}
template <typename T> void write(T x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
  write(x);
  puts("");
}
struct LinkCutTree {
  struct Node {
      int child[2];
      int father, up;
      int size, light;
      bool rev;
  } a[MAXN];
  int size, n;
  void init(int x) {
      n = x;
      for (int i = 1; i <= n; i++)
          a[i].size = 1;
  }
  void update(int root) {
      a[root].size = a[root].light + 1;
      if (a[root].child[0]) a[root].size += a[a[root].child[0]].size;
      if (a[root].child[1]) a[root].size += a[a[root].child[1]].size;
  }
  void pushdown(int root) {
      if (a[root].rev) {
          swap(a[root].child[0], a[root].child[1]);
          if (a[root].child[0]) a[a[root].child[0]].rev ^= true;
          if (a[root].child[1]) a[a[root].child[1]].rev ^= true;
          a[root].rev = false;
      }
  }
  bool get(int x) {
      return a[a[x].father].child[1] == x;
  }
  void rotate(int x) {
      int f = a[x].father, g = a[f].father;
      a[x].up = a[f].up, a[f].up = 0;
      pushdown(f), pushdown(x);
      bool tmp = get(x);
      a[f].child[tmp] = a[x].child[tmp ^ 1];
      if (a[f].child[tmp]) a[a[f].child[tmp]].father = f;
      a[f].father = x;
      a[x].child[tmp ^ 1] = f;
      a[x].father = g;
      if (g) a[g].child[a[g].child[1] == f] = x;
      update(f), update(x);
  }
  void splay(int x) {
      pushdown(x);
      for (int f = a[x].father; (f = a[x].father) != 0; rotate(x))
          if (a[f].father) {
              if (get(x) == get(f)) rotate(f);
              else rotate(x);
          }
  }
  void access(int x) {
      splay(x);
      int tmp = a[x].child[1];
      if (tmp != 0) {
          a[tmp].up = x;
          a[tmp].father = 0;
          a[x].child[1] = 0;
          a[x].light += a[tmp].size;
          update(x);
      }
      while (a[x].up) {
          int f = a[x].up;
          splay(f);
          tmp = a[f].child[1];
          if (tmp != 0) {
              a[tmp].up = f;
              a[tmp].father = 0;
              a[f].light += a[tmp].size;
          }
          a[f].child[1] = x;
          a[f].light -= a[x].size;
          a[x].father = f;
          a[x].up = 0;
          update(f);
          splay(x);
      }
  }
  void link(int x, int y) {
      access(x);
      splay(x);
      reverse(y);
      access(y);
      splay(y);
      a[x].child[1] = y;
      a[y].father = x;
      update(x);
  }
  void reverse(int x) {
      access(x);
      splay(x);
      a[x].rev ^= true;
  }
  long long query(int x, int y) {
      reverse(x);
      access(y);
      splay(x);
      int tmp = a[x].size;
      int tnp = a[y].size;
      return 1ll * (tmp - tnp) * tnp;
  }
} LCT;
int main() {
  int n, m;
  read(n), read(m);
  LCT.init(n);
  for (int i = 1; i <= m; i++) {
      char opt = getchar();
      while (opt != 'A' && opt != 'Q') opt = getchar();
      int x, y; read(x), read(y);
      if (opt == 'A') LCT.link(x, y);
      else writeln(LCT.query(x, y));
  }
  return 0;
}