fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <set>
  8. #include <map>
  9. #include <vector>
  10.  
  11. #define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
  12. #define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
  13.  
  14. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  15. using namespace std;
  16.  
  17. struct Node {
  18.     Node *left, *right, *father;
  19.     int val, key, sum;
  20. } *root, *sentinel;
  21.  
  22. // Must call initTree before using splay tree
  23. void initTree() {
  24.     sentinel = new Node;
  25.     sentinel -> left = sentinel -> right = sentinel -> father = sentinel;
  26.     sentinel -> val = 0;
  27.     sentinel -> key = sentinel -> sum = 0;
  28. }
  29. void setLink(Node *x, Node *y, bool left) {
  30.     if (left) x -> left = y;
  31.     else x -> right = y;
  32.     y -> father = x;
  33. }
  34. void update(Node *x) {
  35.     x -> sum = x->key + x->left->sum + x->right->sum;
  36. }
  37. void upTree(Node *x) {
  38.     Node *y = x -> father;
  39.     Node *z = y -> father;
  40.     Node *tmp;
  41.     if (y->right == x) {
  42.         tmp = x -> left;
  43.         setLink(x, y, true);
  44.         setLink(y, tmp, false);
  45.     }
  46.     else {
  47.         tmp = x -> right;
  48.         setLink(x, y, false);
  49.         setLink(y, tmp, true);
  50.     }
  51.     setLink(z, x, z->left == y);
  52.     update(y); update(x);
  53. }
  54. void splay(Node *x) {
  55.     while (1) {
  56.         Node *y = x -> father;
  57.         if (y == sentinel) return ;
  58.         Node *z = y -> father;
  59.         if (z != sentinel) {
  60.             if ((z->right == y) == (y->right == x)) upTree(y);
  61.             else upTree(x);
  62.         }
  63.         upTree(x);
  64.     }
  65. }
  66. Node *join(Node *t1, Node *t2) {
  67.     if (t1 == sentinel) return t2;
  68.     if (t2 == sentinel) return t1;
  69.     while (1) {
  70.         // refine(t1); // Used for range cover
  71.         if (t1 -> right == sentinel) break;
  72.         t1 = t1 -> right;
  73.     }
  74.     splay(t1);
  75.     setLink(t1, t2, false);
  76.     update(t1);
  77.     return t1;
  78. }
  79.  
  80. const int MN = 200111;
  81. int n, a[MN], father[MN], sign[MN], cur;
  82. vector< int > ke[MN];
  83. Node *nodes[MN], *first[MN], *last[MN];
  84.  
  85. Node *createTree(int l, int r) {
  86.     if (l > r) return sentinel;
  87.     int mid = (l + r) >> 1;
  88.     Node *res = new Node;
  89.     res->left = res->right = res->father = sentinel;
  90.     res->val = a[mid];
  91.     res->key = res->sum = sign[mid];
  92.  
  93.     Node *left = createTree(l, mid - 1);
  94.     Node *right = createTree(mid+1, r);
  95.  
  96.     if (left != sentinel) setLink(res, left, true);
  97.     if (right != sentinel) setLink(res, right, false);
  98.  
  99.     update(res);
  100.     return res;
  101. }
  102.  
  103. Node *access(Node *root, int k) {
  104.     if (root->left->sum >= k) return access(root->left, k);
  105.     k -= root->left->sum;
  106.     if (k == 1 && root->key == 1) return root;
  107.     k -= root->key;
  108.  
  109.     return access(root->right, k);
  110. }
  111.  
  112. void init() {
  113.     FOR(i,1,n) {
  114.         ke[i].clear();
  115.         first[i] = last[i] = sentinel;
  116.     }
  117.     cur = 0;
  118. }
  119.  
  120. void dfs(int u) {
  121.     ++cur; a[cur] = u; sign[cur] = 1;
  122.     REP(i,ke[u].size()) {
  123.         int v = ke[u][i];
  124.         father[v] = u;
  125.         dfs(v);
  126.     }
  127.     ++cur; a[cur] = u; sign[cur] = 0;
  128. }
  129.  
  130. void visitTree(Node *x, string pref = "") {
  131.     if (x == sentinel) return ;
  132.     visitTree(x->left, pref + "  ");
  133.     cout << pref << x->val << ' ' << x->key << ' ' << x->sum << endl;
  134.     visitTree(x->right, pref + "  ");
  135. }
  136.  
  137. #define printTree(x)  { cout << #x << ":" << endl; visitTree(x); }
  138.  
  139. void visit(Node *p) {
  140.     if (p == sentinel) return ;
  141.  
  142.     visit(p->left);
  143.     visit(p->right);
  144.  
  145.     if (p->key) first[p->val] = p;
  146.     else last[p->val] = p;
  147. }
  148.  
  149. int main() {
  150.     int ntest; cin >> ntest;
  151.     while (ntest--) {
  152.         cin >> n;
  153.         initTree();
  154.         init();
  155.         FOR(i,2,n) {
  156.             int u, v; cin >> u >> v;
  157.             ke[u].push_back(v);
  158.         }
  159.         dfs(1);
  160.         // PR(a, n+n);
  161.  
  162.         root = createTree(1, n+n);
  163.         // printTree(root);
  164.  
  165.         visit(root);
  166.  
  167.         // FOR(i,1,n) cout << first[i]->val << ' '; cout << endl;
  168.         // FOR(i,1,n) cout << last[i]->val << ' '; cout << endl;
  169.  
  170.         int q; cin >> q;
  171.         while (q--) {
  172.             // cout << "q = " << q << endl;
  173.             // cerr << q << endl;
  174.             int typ; cin >> typ;
  175.             if (typ == 1) {
  176.                 int u, v; cin >> u >> v;
  177.                 // cout << typ << ' ' << u << ' ' << v << endl;
  178.                 // First, split into 3 parts: [leftmost, first(u)) [first(u), last(u)] and (last[u], rightmost]
  179.                 Node *t2 = first[u]; splay(t2);
  180.                 Node *t1 = t2->left;
  181.                 t2->left = t1->father = sentinel;
  182.                 update(t2);
  183.  
  184.                 t2 = last[u]; splay(t2);
  185.                 Node *t3 = t2->right;
  186.                 t2->right = t3->father = sentinel;
  187.                 update(t2);
  188.  
  189.                 // printTree(t1);
  190.                 // printTree(t2);
  191.                 // printTree(t3);
  192.  
  193.                 t1 = join(t1, t3);
  194.  
  195.                 // Split t1 into 2 parts
  196.                 Node *t4 = last[v]; splay(t4);
  197.                 Node *t5 = t4->left;
  198.                 t4->left = t5->father = sentinel;
  199.                 update(t4);
  200.  
  201.                 // printTree(t4);
  202.                 // printTree(t5);
  203.  
  204.                 root = join(t5, t2);
  205.                 root = join(root, t4);
  206.  
  207.                 // printTree(root);
  208.             } else {
  209.                 int k; cin >> k;
  210.                 // cout << typ << ' ' << k << endl;
  211.                 Node *t = access(root, k);
  212.                 splay(t);
  213.                 root = t;
  214.                 // printTree(root);
  215.                 cout << t->val << endl;
  216.             }
  217.             // cout << "q = " << q << endl;
  218.         }
  219.     }
  220.     return 0;
  221. }
Success #stdin #stdout 0s 10512KB
comments (?)
stdin 
1
7
1 3
1 2
3 5
3 4
2 6
2 7
15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
1 3 2
2 1
2 2
2 3
2 4
2 5
2 6
2 7
stdout 
1
3
5
4
2
6
7
1
2
6
7
3
5
4
https://ideone.com/pldsNB
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!