题意：N个点的有向树， Q次询问， 每次询问区间[L, R]内所有点的LCA。
大致做法：线段树每个点保存它的孩子的LCA值， 对于每一次询问只需要 在线段树查询即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+;
struct Edge{
int to, next;
}e[MAXN << ];
int head[MAXN], tot_edge;
void Add_Edge (int x, int y){
e[tot_edge].to = y;
e[tot_edge].next = head[x];
head[x] = tot_edge++;
}
int n, q, MAX_LOG_V;
bool vis[MAXN];
void init (){
MAX_LOG_V = ;
tot_edge = ;
memset(head, -, sizeof (head));
memset(vis, false, sizeof (vis));
}
int dep[MAXN], pa[][MAXN];
void DFS (int r, int pre, int d){ // DFS 或 BFS都可以， G++下BFS
dep[r] = d;
pa[][r] = pre;
for (int i = head[r]; ~i; i = e[i].next){
int u = e[i].to;
if (pre != u){
DFS(u, r, d+);
}
}
}
void BFS (int r, int pre, int d){
dep[r] = d;
pa[][r] = pre;
queue <int>Q;
Q.push(r);
vis[r] = true;
while (!Q.empty()){
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if (!vis[v]){
dep[v] = dep[u] + ;
pa[][v] = u;
Q.push(v);
vis[v] = true;
}
}
}
}
void pre_solve (){
BFS(, -, );
for (int k = ; k + < MAX_LOG_V; k++){
for (int v = ; v <= n; v++){
if (pa[k][v] < ){
pa[k+][v] = -;
}else{
pa[k+][v] = pa[k][pa[k][v]];
}
}
}
}
int LCA (int u, int v){
if (dep[u] > dep[v]){
swap(u, v);
}
for (int k = ; k < MAX_LOG_V; k++){
if ((dep[v] - dep[u]) >> k & ){
v = pa[k][v];
}
}
if (u == v){
return u;
}
for (int k = MAX_LOG_V-; k >= ; k--){
if (pa[k][u] != pa[k][v]){
u = pa[k][u];
v = pa[k][v];
}
}
return pa[][u];
}
int seg[MAXN << ];
void push_up(int pos){
seg[pos] = LCA(seg[pos<<], seg[pos<<|]);
}
void build (int l, int r, int pos){
if (l == r){
seg[pos] = l;
return ;
}
int mid = (l + r) >> ;
build(l, mid, pos<<);
build(mid+, r, pos<<|);
push_up(pos);
}
int query (int l, int r, int pos, int ua, int ub){
if (ua <= l && ub >= r){
return seg[pos];
}
int mid = (l + r) >> ;
int t1 = -, t2 = -;
if (ua <= mid){
t1 = query(l, mid, pos<<, ua, ub);
}
if (ub > mid){
t2 = query(mid+, r, pos<<|, ua, ub);
}
if (t1 == - || t2 == -){
return max(t1, t2);
}else{
return LCA(t1, t2);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while (~ scanf ("%d", &n)){
init();
for (int i = ; i < n-; i++){
int u, v;
scanf ("%d%d", &u, &v);
Add_Edge(u, v);
Add_Edge(v, u);
}
pre_solve();
build(, n, );
scanf ("%d", &q);
for (int i = ; i < q; i++){
int ua, ub;
scanf ("%d%d", &ua, &ub);
printf("%d\n", query(, n, , ua, ub));
}
}
return ;
}