对于多次询问lca的写法一般有两种……
第一种是离线lca，把询问存进数组，一次dfs处理出所有答案
对于每一个点，dfs到的时候给他加标记，用一个并查集把遍历完的点连起来。
并且对于遍历到的每个点，遍历一遍在这个点上的询问，假设询问的另一个点已经标记过遍历完了，用并查集往上找最后一个更新的他的祖先，这个祖先就是这两个点的lca，存进我们的ans数组即可。
还有一种就是在线的树上倍增lca，原理就是树上倍增优化时间。
先dfs一遍预处理一下往上找距离他2^n（n=0，1，2……）的祖先，顺便求出每个点的深度，对于每次询问先用倍增找到深度更深的那个点和另一个点深度一样的祖先，然后一起往上利用倍增找到距离lca最近的两个祖先，这两个祖先的爸爸就是lca。
代码实现如下
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct edge{
int v,next;
}e[N<<1];
struct st{
int v,id;
};
int eid,h[N],f[N];
void addEdge(int u,int v){
e[eid]={v,h[u]};
h[u]=eid++;
}
void init(int n){
for(int i=1;i<=n;i++)
f[i]=i;
memset(h,-1,sizeof(h));
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
void Union(int u,int v){
u=find(u);
v=find(v);
if(u!=v)f[v]=u;
}
bool vis[N];
vector<st>q[N];
int ans[N];
void dfs(int u,int fa){
vis[u]=1;
for(int i=0;i<q[u].size();i++){
int v=q[u][i].v,id=q[u][i].id;
if(vis[v]){
ans[id]=find(v);
}
}
for(int i=h[u];~i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
Union(u,v);
}
}
int main(){
int n,m,rt;
scanf("%d%d%d",&n,&m,&rt);
init(n);
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
q[u].push_back({v,i});
q[v].push_back({u,i});
}
dfs(rt,-1);
for(int i=0;i<m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct edge{
int v,next;
}e[N<<1];
int eid,h[N];
void addEdge(int u,int v){
e[eid]={v,h[u]};
h[u]=eid++;
}
int par[N][20],vis[N],dep[N];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
par[u][0]=fa;
for(int i=1;i<20;i++){
par[u][i]=par[par[u][i-1]][i-1];
}
for(int i=h[u];~i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;i>=0;i--){
if(dep[par[u][i]]>=dep[v]){
u=par[u][i];
}
}
if(u==v)return v;
for(int i=19;i>=0;i--){
if(par[u][i]!=par[v][i]){
u=par[u][i];
v=par[v][i];
}
}
return par[u][0];
}
int main(){
memset(h,-1,sizeof(h));
int n,m,st;
scanf("%d%d%d",&n,&m,&st);
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
dfs(st,0);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}
设dis[u]是根到u的距离，树上x，y两个点间的距离就是dis[x]+dis[y]-2*dis[lca(x,y)];
然后还有一道例题，用倍增找一条路径中的第k的点。SPOJ - QTREE2
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct edge{
int v,w,next;
}e[N<<1];
int eid,h[N];
void addEdge(int u,int v,int w){
e[eid]={v,w,h[u]};
h[u]=eid++;
}
int dep[N],dis[N];
int par[N][20];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
//printf("#%d\n",dis[u]);
par[u][0]=fa;
for(int i=1;i<20;i++){
par[u][i]=par[par[u][i-1]][i-1];
//printf("#%d\n",par[u][i-1]);
}
for(int i=h[u];~i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(v==fa)continue;
dis[v]=dis[u]+w;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;i>=0;i--){
if(dep[par[u][i]]>=dep[v]){
u=par[u][i];
}
}
if(u==v)return v;
for(int i=19;i>=0;i--){
if(par[u][i]!=par[v][i]){
u=par[u][i];
v=par[v][i];
}
}
return par[u][0];
}
int getPar(int u,int k){
k-=1;
int res=u;
for(int i=0;i<20;i++){
if((k>>i)&1){
res=par[res][i];
}
}
return res;
}
int main(){
int _;
scanf("%d",&_);
while(_--){
int n;
scanf("%d",&n);
eid=0;
memset(h,-1,sizeof(h));
memset(par,0,sizeof(par));
memset(dis,0,sizeof(dis));
for(int i=0;i<n-1;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
dfs(1,0);
char temp[10];
while(scanf("%s",temp)!=EOF){
if(temp[2]=='N')break;
if(temp[2]=='S'){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
// printf("#%d\n",lca(u,v));
}
else if(temp[2]=='H'){
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
int nowLca=lca(u,v);
int dDepU=dep[u]-dep[nowLca]+1;
int dDepV=dep[v]-dep[nowLca]+1;
if(k>dDepU){
printf("%d\n",getPar(v,dDepV-(k-dDepU)));
}else
printf("%d\n",getPar(u,k));
}
}
if(_)puts("");
}
return 0;
}