题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5266
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll unsigned long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn =3e5+5;
const int mod=9999991;
const int ub=1e6;
///const double e=2.71828;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
明显lca具有区间性质，
直接用线段树维护下即可。*/
///链式前向星
struct node
{int u,nxt;
}e[maxn<<1];
int head[maxn],tot=0;
void add(int x,int y)
{e[tot]=node{y,head[x]};head[x]=tot++;
}
///动态倍增lca
int dep[maxn],pa[maxn][20];
void init()
{mst(head,-1),mst(pa,0);tot=dep[1]=0;
}
void dfs(int u,int pre)
{pa[u][0]=pre;for(int i=1;i<20;i++) pa[u][i]=pa[pa[u][i-1]][i-1];for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==pre) continue;dep[v]=dep[u]+1;dfs(v,u);}
}
int lca(int u,int v)
{int i,j;if(dep[u]<dep[v]) swap(u,v);for(i=0;(1<<i)<=dep[u];i++);i--;for(j=i;j>=0;j--) if(dep[u]-(1<<j)>=dep[v]) u=pa[u][j];if(u==v) return u;for(j=i;j>=0;j--) if(pa[u][j]&&pa[u][j]!=pa[v][j])u=pa[u][j],v=pa[v][j];return pa[u][0];
}
///用线段树维护lca区间
int tree[maxn<<2];
void pushup(lrt)
{tree[rt]=lca(tree[rt<<1],tree[rt<<1|1]);
}
void build(lrt)
{if(l==r) {tree[rt]=l;return ;}int mid=l+r>>1;build(lson),build(rson),pushup(root);
}
int query(lrt,int L,int R)
{if(L<=l&&r<=R){return tree[rt];}int mid=l+r>>1,tl=-1,tr=-1;if(L<=mid) tl=query(lson,L,R);if(mid<R) tr=query(rson,L,R);if(tl!=-1&&tr!=-1) return lca(tl,tr);else return tl==-1?tr:tl;
}int n,q,a,b;int main()
{while(scanf("%d",&n)!=EOF){init();for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b),add(b,a);}dfs(1,0);///cout<<lca(1,2)<<endl;build(1,n,1);///debugscanf("%d",&q);while(q--){scanf("%d%d",&a,&b);printf("%d\n",query(1,n,1,a,b));}}return 0;
}