lib/Documentation/docs-sonyckson/QTREE3.cpp

   1 // SEGMENT TREES! :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 vector<int> edges[MAXN];
  35 int N, Q;
  36 struct node{
  37         int first, val, begin, end;
  38 };
  39 struct STREE{
  40         int size;
  41         vector<node> vec;
  42         void create(int node, int begin, int end){
  43                 vec[node].begin = begin; vec[node].end = end;
  44                 vec[node].first = -1, vec[node].val = 0;
  45                 if( begin == end )return;
  46                 create(2*node,begin,(end+begin)/2);
  47                 create(2*node+1,(end+begin)/2+1,end);
  48         }
  49         STREE(int x){
  50                 size = x;
  51                 int pot = 1;
  52                 while( pot < x ) pot *=2;
  53                 pot *= 2;
  54                 vec.resize(pot+1);
  55                 create(1,0,x-1);
  56         }
  57         // indexado en 0...
  58         void change(int node, int pos){
  59                 if( vec[node].begin != vec[node].end ){
  60                         if( pos <= (vec[node].begin+vec[node].end)/2 )change(2*node,pos);
  61                         else change(2*node+1,pos);
  62                         if( vec[2*node].first !=-1 ) vec[node].first = vec[2*node].first;
  63                         else if( vec[2*node+1].first != -1 ) vec[node].first = vec[2*node+1].first;
  64                         else vec[node].first = -1;
  65                         return;
  66                 }
  67                 assert( vec[node].begin == pos);
  68                 vec[node].val = 1 - vec[node].val;
  69                 if( vec[node].val ) vec[node].first = vec[node].begin;
  70                 else vec[node].first = -1;
  71
  72         }
  73         bool inrange(int pos, int node){
  74                 if( pos >= vec[node].begin && pos <= vec[node].end) return true;
  75                 return false;
  76         }
  77         int query(int node, int end){
  78                 if( vec[node].end <= end )return vec[node].first;
  79                 if( vec[node].begin > end )return -1;
  80                 if( vec[node].begin == vec[node].end ) return -1;
  81                 int a;
  82                 if( inrange(end,2*node)){a= query(2*node,end);if(a>=0) return a;}
  83                 if( inrange(end,2*node+1)){a = query(2*node+1,end); if( a>=0) return a;}
  84                 return -1;
  85         }
  86 };
  87 int ind;
  88 vector<STREE> streeVec;
  89 vector<vector<int> > nodosVec;
  90 int depth[MAXN],chain[MAXN], prev[MAXN];
  91 int prevStree[MAXN], homeStree[MAXN], homeIndex[MAXN];
  92 int dep(int node){if( node < 0 ) return -1; return depth[node];}
  93 vector<int> nodos;
  94
  95 void constructStree(){
  96         if(nodos.size() == 0 ) return;
  97         int i,j ,k;
  98         for(i=0;i<nodos.size();i++){
  99                 prevStree[nodos[i]] = prev[nodos[0]];
 100                 homeStree[nodos[i]] = ind;
 101                 homeIndex[nodos[i]] = i;
 102         }
 103         ind++;
 104         streeVec.PB(STREE(nodos.size()));
 105         nodosVec.PB(nodos);
 106 }
 107 void go(int node, int father){
 108         nodos.push_back(node);
 109         if( edges[node].size() == 1 && edges[node][0] == father ) constructStree();
 110         int i,j ,k;
 111         int larger = -1;
 112         for(i=0;i<edges[node].size();i++){
 113                 if( edges[node][i] == father ) continue;
 114                 if( dep(edges[node][i]) > dep(larger) ) larger = edges[node][i];
 115         }
 116         if( larger >= 0 )go(larger,node);
 117         for(i=0;i<edges[node].size();i++){
 118                 if( edges[node][i] == father ) continue;
 119                 if( edges[node][i] != larger ){
 120                         nodos.clear(); go(edges[node][i],node);
 121                 }
 122         }
 123 }
 124 void dfs(int node, int father){
 125         prev[node] = father;
 126         int i,j ,k;
 127         for(i=0;i<edges[node].size();i++){
 128                 if( edges[node][i] == father ) continue;
 129                 dfs(edges[node][i], node);
 130         }
 131         depth[node] = 0;
 132         for(i=0;i<edges[node].size();i++){
 133                 if( edges[node][i] == father ) continue;
 134                 depth[node] = max( depth[node], depth[edges[node][i]]+1);
 135         }
 136 }
 137 void query(int node){
 138         int stree = homeStree[node];
 139         int f = streeVec[stree].query( 1,  homeIndex[node] );
 140         int nod = -1;
 141         if( f >= 0 ) nod = nodosVec[stree][f];
 142         int last = prevStree[node];
 143         while( last != -1 ){
 144                 stree = homeStree[last];
 145                 int aux = streeVec[stree].query( 1,  homeIndex[last] );
 146                 if( aux >= 0 ){
 147                         f = aux;
 148                         nod = nodosVec[stree][f];
 149                 }
 150                 last = prevStree[last];
 151         }
 152         if(nod == -1 ) nod--;
 153         printf("%i\n", nod+1);
 154 }
 155 void change(int node){
 156         int stree = homeStree[node];
 157         streeVec[stree].change( 1, homeIndex[node]);
 158 }
 159 int main(){
 160         int i,j ,k;
 161         memset(depth, -1, sizeof(depth));
 162         scanf("%i %i", &N, &Q);
 163         for(i=0;i<N-1;i++){
 164                 int a, b;
 165                 scanf("%i %i", &a, &b);a--, b--;
 166                 edges[a].PB(b), edges[b].PB(a);
 167         }
 168         dfs(0,-1);
 169         ind = 0;
 170         go(0,-1);
 171         for(i=0;i<Q;i++){
 172                 int op, node;
 173                 scanf("%i %i", &op, &node);
 174                 node--;
 175                 if( op ) query(node);
 176                 else change(node);
 177         }return 0;
 178 }