板子-JZTXT

LCT

struct LinkCutTree {
   struct Node {
      int ch[2]; 
      int fa; 
      int rev_tag; 
      // ...
   }; 
   
   vector<Node> tree; 
   
   map<pair<int, int>, bool> edge; 
   
   void init(int n /* ... */) {
      tree.resize(n + 10); 
      for (int i = 1; i <= n; ++i) {
         tree[i].ch[0] = tree[i].ch[1] = tree[i].fa = tree[i].rev_tag = 0; 
         // ...
   	}
   }
   
   void pushUp(int x) {
      // ...
   }
   
   void pushDown(int x) {
      if (tree[x].rev_tag) {
         swap(tree[tree[x].ch[0]].ch[0], tree[tree[x].ch[0]].ch[1]); 
         tree[tree[x].ch[0]].rev_tag ^= 1; 
         swap(tree[tree[x].ch[1]].ch[0], tree[tree[x].ch[1]].ch[1]); 
         tree[tree[x].ch[1]].rev_tag ^= 1; 
         tree[x].rev_tag = 0; 
      }
      // ...
   }
   
   int get(int x) { return tree[tree[x].fa].ch[1] == x; }
   
   int isRoot(int x) { return tree[tree[x].fa].ch[0] != x && tree[tree[x].fa].ch[1] != x; }
   
   void rotate(int x) {
      int y = tree[x].fa, z = tree[y].fa, t = get(x); 
      if (!isRoot(y)) tree[z].ch[get(y)] = x; 
      tree[y].ch[t] = tree[x].ch[t ^ 1], tree[tree[x].ch[t ^ 1]].fa = y; 
      tree[x].ch[t ^ 1] = y, tree[y].fa = x; 
      tree[x].fa = z; 
      pushUp(y); 
   }
   
   void update(int x) {
      if (!isRoot(x)) update(tree[x].fa); 
      pushDown(x); 
   }
   
   void splay(int x) {
      update(x); 
      for (int fa = tree[x].fa; !isRoot(x); rotate(x), fa = tree[x].fa) {
         if (!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x); 
      }
      pushUp(x);  
   }
   
   int access(int x) {
      splay(x); 
      tree[x].ch[1] = 0, pushUp(x); 
      while (tree[x].fa) {
         int fa = tree[x].fa; 
         splay(fa), tree[fa].ch[1] = x, pushUp(fa); 
         x = fa; 
      }
      return x; 
   }
   
   void makeRoot(int x) {
      access(x), splay(x); 
      swap(tree[x].ch[0], tree[x].ch[1]); 
      tree[x].rev_tag ^= 1; 
   }
   
   int findRoot(int x) {
      x = access(x); 
      pushDown(x); 
      while (tree[x].ch[0]) x = tree[x].ch[0], pushDown(x); 
      splay(x); 
      return x; 
   }
   
   void link(int x, int y) {
      if (findRoot(x) == findRoot(y)) return; 
      makeRoot(x), tree[x].fa = y; 
      edge[make_pair(x, y)] = edge[make_pair(y, x)] = 1; 
   }
   
   void cut(int x, int y) {
      if (!edge[make_pair(x, y)]) return; 
      makeRoot(x), access(x), splay(y), tree[y].fa = 0; 
      edge[make_pair(x, y)] = edge[make_pair(y, x)] = 0; 
   }
   
   int split(int x, int y) {
      makeRoot(x); 
      return access(y); 
   }
   
   // ...
} LCT;