lib/Documentation/docs-sonyckson/QTREE3opt.cpp

   1 // SEGMENT TREES VERY SIMPLE'S!!! :D...
   2 #include <algorithm>
   3 #include <vector>
   4 #include <set>
   5 #include <string>
   6 #include <fstream>
   7 #include <iostream>
   8 #include <iomanip>
   9 #include <map>
  10 #include <sstream>
  11 #include <queue>
  12 #include <cassert>
  13 #include <cmath>
  14 #include <cstdio>
  15 #include <cctype>
  16 #include <cstdlib>
  17 #include <cstring>
  18
  19 #define forn(i, n) for(int i=0;i<int(n);i++)
  20 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  21 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  22 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  23 #define ALL(x)   (x).begin(),(x).end()
  24 #define SIZE(x)   (int)(x).size()
  25 #define SORT(x) sort(ALL(x))
  26 using namespace std;
  27 #define VI vector<int>
  28 #define VS vector<string>
  29 #define PB push_back
  30 #define ISS istringstream
  31 #define OSS ostringstream
  32 typedef long long ll;
  33 #define MAXN 100010
  34
  35
  36 // SEGMENT TREES! :D...
  37 #include <algorithm>
  38 #include <vector>
  39 #include <set>
  40 #include <string>
  41 #include <fstream>
  42 #include <iostream>
  43 #include <iomanip>
  44 #include <map>
  45 #include <sstream>
  46 #include <queue>
  47 #include <cassert>
  48 #include <cmath>
  49 #include <cstdio>
  50 #include <cctype>
  51 #include <cstdlib>
  52 #include <cstring>
  53
  54 #define forn(i, n) for(int i=0;i<int(n);i++)
  55 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  56 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  57 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  58 #define ALL(x)   (x).begin(),(x).end()
  59 #define SIZE(x)   (int)(x).size()
  60 #define SORT(x) sort(ALL(x))
  61 using namespace std;
  62 #define VI vector<int>
  63 #define VS vector<string>
  64 #define PB push_back
  65 #define ISS istringstream
  66 #define OSS ostringstream
  67 typedef long long ll;
  68 #define MAXN 100010
  69 vector<int> edges[MAXN];
  70 int N, Q;
  71 struct node{
  72         int first, val, begin, end;
  73 };
  74 struct STREE{
  75         int size;
  76         int off;
  77         vector<int> vec;
  78         STREE(int x){
  79                 size = x-1;
  80                 int pot = 1;
  81                 while( pot < x ) pot *=2;
  82                 off = pot;
  83                 pot *= 2;
  84                 vec.resize(pot+1,-1);
  85         }
  86         // indexado en 0...
  87         void change(int node, int pos){
  88                 if( vec[pos+off] >= 0 ) vec[pos+off] = -1;
  89                 else vec[pos+off] = pos;
  90 //              printf("%i %i\n", pos, vec[pos+off]);
  91                 for(int x = (off+pos)/2;x>=1;x/=2){
  92                         if( vec[2*x] >= 0 ) vec[x] = vec[2*x];
  93                         else if( vec[2*x+1] >= 0 ) vec[x] = vec[2*x+1];
  94                         else vec[x] = -1;
  95 //                      printf("%i %i\n", x, vec[x]);
  96                 }
  97         }
  98         int query(int node,int end,int begin, int a, int b){
  99 //              printf("%i %i %i %i %i %i\n", node, begin, end, a, b, vec[node]);
 100                 if( a > end  || b < begin ) return -1;
 101                 if( a >= begin && b <= end) return vec[node];
 102                 int r = query(node*2,end,begin,a,(a+b)/2);
 103                 int s = query(node*2+1,end,begin,(a+b)/2+1,b);
 104                 if( r >= 0 ) return r;
 105                 if( s >= 0 ) return s;
 106                 return -1;
 107         }
 108 };
 109 int ind;
 110 vector<STREE> streeVec;
 111 vector<vector<int> > nodosVec;
 112 int depth[MAXN],chain[MAXN], prev[MAXN];
 113 int prevStree[MAXN], homeStree[MAXN], homeIndex[MAXN];
 114 int dep(int node){if( node < 0 ) return -1; return depth[node];}
 115 vector<int> nodos;
 116
 117 void constructStree(){
 118         if(nodos.size() == 0 ) return;
 119         int i,j ,k;
 120         for(i=0;i<nodos.size();i++){
 121                 prevStree[nodos[i]] = prev[nodos[0]];
 122                 homeStree[nodos[i]] = ind;
 123                 homeIndex[nodos[i]] = i;
 124         }
 125         ind++;
 126         streeVec.PB(STREE(nodos.size()));
 127         nodosVec.PB(nodos);
 128 }
 129 void go(int node, int father){
 130         nodos.push_back(node);
 131         if( edges[node].size() == 1 && edges[node][0] == father ) constructStree();
 132         int i,j ,k;
 133         int larger = -1;
 134         for(i=0;i<edges[node].size();i++){
 135                 if( edges[node][i] == father ) continue;
 136                 if( dep(edges[node][i]) > dep(larger) ) larger = edges[node][i];
 137         }
 138         if( larger >= 0 )go(larger,node);
 139         for(i=0;i<edges[node].size();i++){
 140                 if( edges[node][i] == father ) continue;
 141                 if( edges[node][i] != larger ){
 142                         nodos.clear(); go(edges[node][i],node);
 143                 }
 144         }
 145 }
 146 void dfs(int node, int father){
 147         prev[node] = father;
 148         int i,j ,k;
 149         for(i=0;i<edges[node].size();i++){
 150                 if( edges[node][i] == father ) continue;
 151                 dfs(edges[node][i], node);
 152         }
 153         depth[node] = 0;
 154         for(i=0;i<edges[node].size();i++){
 155                 if( edges[node][i] == father ) continue;
 156                 depth[node] = max( depth[node], depth[edges[node][i]]+1);
 157         }
 158 }
 159 void query(int node){
 160         int stree = homeStree[node];
 161         int f = streeVec[stree].query( 1,  homeIndex[node],0,0,streeVec[stree].off-1);
 162         int nod = -1;
 163         if( f >= 0 ) nod = nodosVec[stree][f];
 164         int last = prevStree[node];
 165 //      printf("%i %i %i\n", stree, f, last);
 166 //      return;
 167         while( last != -1 ){
 168 //              printf("ENTERS\n");
 169                 stree = homeStree[last];
 170                 int aux = streeVec[stree].query( 1,  homeIndex[last] ,0,0,streeVec[stree].off-1);
 171 //              printf("stree %i.. last %i ... ax %i\n", stree, last, aux);
 172                 if( aux >= 0 ){
 173                         f = aux;
 174                         nod = nodosVec[stree][f];
 175                 }
 176                 last = prevStree[last];
 177         }
 178         if(nod == -1 ) nod--;
 179         printf("%i\n", nod+1);
 180 }
 181 void change(int node){
 182         int stree = homeStree[node];
 183         streeVec[stree].change( 1, homeIndex[node]);
 184 }
 185 int main(){
 186         int i,j ,k;
 187         memset(depth, -1, sizeof(depth));
 188         scanf("%i %i", &N, &Q);
 189         for(i=0;i<N-1;i++){
 190                 int a, b;
 191                 scanf("%i %i", &a, &b);a--, b--;
 192                 edges[a].PB(b), edges[b].PB(a);
 193         }
 194         dfs(0,-1);
 195         ind = 0;
 196         go(0,-1);
 197         for(i=0;i<Q;i++){
 198                 int op, node;
 199                 scanf("%i %i", &op, &node);
 200                 node--;
 201                 if( op ) query(node);
 202                 else change(node);
 203         }return 0;
 204 }