peltorator

Link-Cut Tree

Jul 7th, 2017
139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Node
  2. {
  3.     Node *left;
  4.     Node *right;
  5.     Node *parent;
  6.     Node *link;
  7.     int x;
  8.     bool rev;
  9.     Node(int x = 0):
  10.         left(0),
  11.         right(0),
  12.         parent(0),
  13.         link(0),
  14.         x(x),
  15.         rev(0){}
  16.    
  17. };
  18.  
  19. void push(Node *v)
  20. {
  21.     if (v == NULL || !v->rev)
  22.         return;
  23.     v->rev = 0;
  24.     swap(v->left, v->right);
  25.     if (v->left != NULL)
  26.         v->left->rev ^= 1;
  27.     if (v->right != NULL)
  28.         v->right->rev ^= 1;
  29. }
  30.  
  31. Node* zig(Node *v)
  32. {
  33.     push(v->parent);
  34.     push(v);
  35.     Node *u = v->parent;
  36.     if (u->left == v)
  37.     {
  38.         u->left = v->right;
  39.         if (u->left != NULL)
  40.             u->left->parent = u;
  41.         v->right = u;
  42.         v->parent = u->parent;
  43.         if (u->parent != NULL)
  44.         {
  45.             if (u->parent->left == u)
  46.                 u->parent->left = v;
  47.             else
  48.                 u->parent->right = v;
  49.         }
  50.         u->parent = v;
  51.     }
  52.     else
  53.     {
  54.         u->right = v->left;
  55.         if (u->right != NULL)
  56.             u->right->parent = u;
  57.         v->left = u;
  58.         v->parent = u->parent;
  59.         if (u->parent != NULL)
  60.         {
  61.             if (u->parent->left == u)
  62.                 u->parent->left = v;
  63.             else
  64.                 u->parent->right = v;
  65.         }
  66.         u->parent = v;
  67.     }
  68.     return v;
  69. }
  70.  
  71.  
  72. Node* zigzig(Node *v)
  73. {
  74.     Node *u = v->parent;
  75.     u = zig(u);
  76.     v = zig(v);
  77.     return v;
  78. }
  79.  
  80. Node* zigzag(Node *v)
  81. {
  82.     v = zig(v);
  83.     v = zig(v);
  84.     return v;
  85. }
  86.  
  87. Node* splay(Node *v)
  88. {
  89.     while (true)
  90.     {
  91.         if (v->parent == NULL)
  92.             return v;
  93.         if (v->parent->parent == NULL)
  94.         {
  95.             v = zig(v);
  96.             return v;
  97.         }
  98.         push(v->parent->parent);
  99.         push(v->parent);
  100.         if (v->parent->parent->left == v->parent && v->parent->left == v)
  101.             v = zigzig(v);
  102.         else if (v->parent->parent->right == v->parent && v->parent->right == v)
  103.             v = zigzig(v);
  104.         else
  105.             v = zigzag(v);
  106.     }
  107. }
  108.  
  109. Node* root(Node *u)
  110. {
  111.     Node *v = u;
  112.     while (v->parent != NULL)
  113.         v = v->parent;
  114.     return v;
  115. }
  116.  
  117. Node* left(Node *v)
  118. {
  119.     Node *u = root(v);
  120.     push(u);
  121.     while (u->left != NULL)
  122.     {
  123.         u = u->left;
  124.         push(u);
  125.     }
  126.     return u;
  127. }
  128.  
  129. Node* right(Node *v)
  130. {
  131.     Node *u = root(v);
  132.     push(v);
  133.     while (u->right != NULL)
  134.     {
  135.         u = u->right;
  136.         push(u);
  137.     }
  138.     return u;
  139. }
  140.  
  141. pair<Node*, Node*> split(Node *v)
  142. {
  143.     v = splay(v);
  144.     push(v);
  145.     Node *u = v->left;
  146.     v->left = NULL;
  147.     if (u != NULL)
  148.         u->parent = NULL;
  149.     return {u, v};
  150. }
  151.  
  152. Node* merge(Node *l, Node *r)
  153. {
  154.     if (l == NULL)
  155.         return r;
  156.     if (r == NULL)
  157.         return l;
  158.     Node *u = right(l);
  159.     u = splay(u);
  160.     push(u);
  161.     u->right = r;
  162.     r->parent = u;
  163.     return u;
  164. }
  165.  
  166. Node* find1(Node *v, int key)
  167. {
  168.     push(v);
  169.     if (!v)
  170.         return NULL;
  171.     if (v->x == key)
  172.         return v;
  173.     if (v->x < key)
  174.         return find1(v->right, key);
  175.     Node *ret = find1(v->left, key);
  176.     if (ret == NULL)
  177.         return v;
  178.     return ret;
  179. }
  180.  
  181. Node* find(Node *v, int key)
  182. {
  183.     return find1(root(v), key);
  184. }
  185.  
  186.  
  187. Node* findright(Node *v)
  188. {
  189.     return right(v);
  190.     Node *u = root(v);
  191.     while (u->right != NULL)
  192.         u = u->right;
  193.     return u;
  194. }
  195.  
  196. Node* findleft(Node *v)
  197. {
  198.     return left(v);
  199.     Node *u = root(v);
  200.     while (u->left != NULL)
  201.         u = u->left;
  202.     return u;
  203. }
  204.  
  205.  
  206. pair<Node*, Node*> split(Node *v, int key)
  207. {
  208.     if (!v)
  209.         return {NULL, NULL};
  210.     Node *u = find(v, key);
  211.     Node *r = findright(v);
  212.     if (r->x < key)
  213.         return {v, NULL};
  214.     return split(u);
  215. }
  216.  
  217.  
  218. Node* insert(Node *v, int key)
  219. {
  220.     auto a = split(v, key);
  221.     if (a.second != NULL && findleft(a.second)->x == key)
  222.         return merge(a.first, a.second);
  223.     v = merge(a.first, merge(new Node(key), a.second));
  224.     return v;
  225. }
  226.  
  227. void gogo(Node *v)
  228. {
  229.     if (!v)
  230.         return;
  231.     push(v);
  232.     gogo(v->left);
  233.     cout << v->x << ' ';
  234.     gogo(v->right);
  235. }
  236.  
  237. const int N = 100001;
  238.  
  239. Node* vert[N];
  240. int pr[N];
  241.  
  242.  
  243. void expose(int x)
  244. {
  245.     Node *v = vert[x];
  246.     Node *last = NULL;
  247.     while (true)
  248.     {
  249.         if (!v)
  250.             return;
  251.         Node *r = root(v);
  252.         Node *nxt = r->link;
  253.         r->link = NULL;
  254.         auto a = split(v);
  255.         if (a.first != NULL)
  256.             a.first->link = v;
  257.         merge(last, a.second);
  258.         last = root(v);
  259.         v = nxt;
  260.     }
  261. }
  262.  
  263. void makeRoot(int v)//not shure that it works(reverse also)
  264. {
  265.     expose(v);
  266.     splay(vert[v]);
  267.     vert[v]->rev ^= 1;
  268.     push(vert[v]);
  269. }
  270.  
  271. void link(int v, int u)
  272. {
  273.     splay(vert[v]);
  274.     vert[v]->link = vert[u];
  275.     pr[v] = u;
  276. }
  277.  
  278. void cut(int v, int u)
  279. {
  280.     if (pr[v] != u)
  281.         swap(v, u);
  282.     pr[v] = v;
  283.     expose(u);
  284.     Node *t = root(vert[v]);
  285.     t->link = NULL;
  286. }
  287.  
  288. bool connected(int x, int y)
  289. {
  290.     expose(x);
  291.     int fir = findright(root(vert[x]))->x;
  292.     expose(y);
  293.     int sec = findright(root(vert[y]))->x;
  294.     return fir == sec;
  295. }
  296.  
  297. int lca(int x, int y)
  298. {
  299.     expose(x);
  300.     expose(y);
  301.     if (root(vert[x])->x == root(vert[y])->x)
  302.         return x;
  303.     return root(vert[x])->link->x;
  304. }
  305.  
  306. void build(int n)
  307. {
  308.     for (int i = 1; i <= n; i++)
  309.         vert[i] = new Node(i);
  310. }
RAW Paste Data