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 lili to riri ([li,ri])([li,ri]).
Input
Several groups of data (no more than 3 groups,n≥10000n≥10000 or Q≥10000Q≥10000).
The following line contains ans integers,n(2≤n≤300000)n(2≤n≤300000).
AT The following n−1n−1 line, two integers are bibi and cici at every line, it shows an edge connecting bibi and cici.
The following line contains ans integers,Q(Q≤300000)Q(Q≤300000).
AT The following QQ line contains two integers li and ri(1≤li≤ri≤n1≤li≤ri≤n).
Output
For each case,output QQ integers means the LCA of [li,ri][li,ri].
Sample Input
5
1 2
1 3
3 4
4 5
5
1 2
2 3
3 4
3 5
1 5 Sample Input 1
1
3
1
1 一顆樹以1為根節點，給出區間範圍，求範圍内所有點的lca公共祖先，之前學的lca算法隻能求兩個點的，但考慮到是區間内進行操作，故考慮線段樹。這道題如果了解線段樹的話可以說沒什麼難度了...
做這道題這道題之前，沒學過線段樹...搞了好久才弄清楚，在網上抄了個線段樹模闆，弄清楚後沒有想象中的難，實際上就是簡單的lca+線段樹組合罷了，可以說是模闆題也不為過，收獲就是學會了bfs樹上倍增和搞清楚了線段樹吧，
這個資料結構挺神奇的。
該題G++送出會TLE，C++送出如果不手動擴棧就會爆棧，當然也可以用BFS倍增就不用擔心爆棧了。
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\n", ans );
159 }
160 }
161 return 0;
162 } 轉載于:https://www.cnblogs.com/chaoswr/p/8490400.html