HDU 5266 pog loves szh III 线段树，lca

Pog and Szh are playing games. Firstly Pog draw a tree on the paper. Here we define 1 as the root of the tree.Then Szh choose some nodes from the tree. He wants Pog helps to find the least common ancestor (LCA) of these node.The question is too difficult for Pog.So he decided to simplify the problems.The nodes picked are consecutive numbers from $l_{i}$

$l_{i}$

$l_{i}$

$l_{i}$

$l_{i}$

$l_{i}$

 $l_{i}$

 $l_{i}$

 $l_{i}$

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <math.h>
  5 #include <cstdio>
  6 #include <queue>
  7 #pragma warning ( disable : 4996 )
  8 #pragma comment(linker, "/STACK:102400000,102400000")  //防止爆栈
  9 
 10 using namespace std;
 11 
 12 int Max( int x, int y ) { return x>y?x:y; }
 13 int Min( int x, int y ) { return x>y?y:x; }
 14 
 15 const int inf = 0x3f3f3f3f;
 16 const int vspot = 3e5 + 5;
 17 const int espot = 1e5 + 5;
 18 
 19 struct node {
 20     int from, to, next;
 21 }e[vspot<<1];
 22 
 23 int N, Q, cnt, logn;
 24 int lca[vspot<<2], linjie[vspot];
 25 int fa[vspot][22], depth[vspot];
 26 
 27 void addedge(int u, int v)
 28 {
 29     e[cnt].from = u; e[cnt].to = v;
 30     e[cnt].next = linjie[u]; linjie[u] = cnt++;
 31     e[cnt].from = v; e[cnt].to = u;
 32     e[cnt].next = linjie[v]; linjie[v] = cnt++;
 33 }
 34 
 35 void init()
 36 {
 37     cnt = 0;
 38     logn = 20;
 39     memset( linjie, -1, sizeof(linjie) );
 40     memset( lca, 0, sizeof(lca) );
 41     memset( depth, 0, sizeof(depth) );
 42     memset( fa, 0, sizeof(fa) );
 43 }
 44 
 45 void dfs( int x )
 46 {
 47     for( int i = 1; i <= logn; i++ )
 48         if ( fa[x][i-1] )
 49             fa[x][i] = fa[fa[x][i-1]][i-1];
 50         else
 51             break;
 52     for ( int i = linjie[x]; i+1; i = e[i].next )
 53         if ( fa[x][0] != e[i].to )
 54         {
 55             fa[e[i].to][0] = x;
 56             depth[e[i].to] = depth[x]+1;
 57             dfs(e[i].to);
 58         }
 59 }
 60 
 61 void bfs( int x )
 62 {
 63     queue<int> Q;
 64     Q.push(x);
 65 
 66     while (!Q.empty())
 67     {
 68         int run = Q.front();
 69         Q.pop();
 70         for( int i = linjie[run]; i+1; i = e[i].next )
 71             if ( fa[run][0] != e[i].to )
 72             {
 73                 fa[e[i].to][0] = run;
 74                 depth[e[i].to] = depth[run] + 1;
 75                 Q.push(e[i].to);
 76             }
 77     }
 78 }
 79 
 80 void init2()
 81 {
 82     for ( int i = 0; i <= logn; i++ )
 83         for ( int x = 1; x <= N; x++ )
 84             fa[x][i+1] = fa[fa[x][i]][i];
 85 }
 86 
 87 int Lca( int u, int v )
 88 {
 89     if ( depth[u] < depth[v] )
 90         swap(u,v);
 91     int d = depth[u] - depth[v];
 92     for ( int i = 0; i <= logn; i++ )
 93         if( (1<<i)&d )
 94             u = fa[u][i];
 95 
 96     if ( u == v ) return u;
 97     for ( int i = logn; i >= 0; i-- )
 98         if ( fa[u][i] != fa[v][i] )
 99         {
100             u = fa[u][i];
101             v = fa[v][i];
102         }
103     return fa[u][0];
104 }
105 
106 void pushUp( int pos ) { lca[pos] = Lca(lca[pos<<1], lca[pos<<1|1]); }
107 
108 void build( int lhs, int rhs, int id )
109 {
110     if ( lhs == rhs )
111     {
112         lca[id] = lhs;
113         return;
114     }
115     int mid = ( lhs + rhs ) >> 1;
116     build( lhs, mid, id<<1 );
117     build( mid+1, rhs, id<<1|1 );
118 
119     pushUp(id);
120 }
121 
122 //lhs, rhs表示当前节点的区间，l，r表示要操作的区间
123 int query( int lhs, int rhs, int l, int r, int id )
124 {
125     if ( l <= lhs && r >= rhs )
126         return lca[id];
127     int mid = (lhs+rhs)>>1;
128 
129     int llca = -1, rlca = -1;
130     if ( l <= mid ) llca = query( lhs, mid, l, r, id<<1 );
131     if ( r >  mid ) rlca = query( mid+1, rhs, l, r, id<<1|1 );
132 
133     if ( llca == -1 || rlca == -1 )
134         return Max(llca, rlca);
135     else
136         return Lca(llca, rlca);
137 }
138 
139 int main()
140 {
141     while ( ~scanf("%d", &N) )
142     {
143         init();
144         int x, y;
145         for( int i = 1; i < N; i++ )
146             { scanf("%d %d", &x, &y ); addedge(x,y); }
147         bfs(1);
148         init2();
149         // dfs(1);   用dfs并去掉上面两行也行
150         build(1,N,1);
151         
152         cin >> Q;
153         int ans;
154         for ( int i = 1; i <= Q; i++ ) 
155         {
156             scanf( "%d %d", &x, &y );
157             ans = query( 1, N, x, y, 1 );
158             printf( "%d
", ans );
159         }
160     }
161     return 0;
162 }

 $l_{i}$