第一种：树上倍增
f[x,k]表示x的2^k辈祖先，即x向根结点走2^k步达到的结点。
初始条件：f[x][0]=fa[x]
递推式：f[x][k]=f[ f[x][k-1] ][k-1]
一次bfs预处理f数组（nlogn），然后每次询问都可以在（logn）时间内求出x,y的lca
求lca的步骤
1.令x的深度大于y，然后通过二进制拆分将x上调到与y同一个深度（依次用k=2^logn,...2^1,2^0试探）
2.如果此时x==y,那么y=lca(x,y),算法结束
3.继续用第一步的二进制拆分法同时将x,y往上提，保持深度一致，并且两者不可以相会
4.最后f[x][0]=f[y][0]=lca(x,y)
注意第三步，x，y不可以相会！
int f[maxn][],d[maxn],t;
void bfs(){
queue<int>q;
q.push();d[]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(d[v])continue;
f[v][]=u;
d[v]=d[u]+;
for(int k=;k<=;k++)
f[v][k]=f[f[v][k-]][k-];
q.push(v);
}
}
}
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return y;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][];
}
第二种，tarjan+并查集优化，离线算法
首先说明最简单的向上标记法：x,y沿着边不停往上寻找lca，直到相遇，相遇点就是lca
使用并查集对“向上标记法”进行优化
在tarjan算法的dfs过程中，所有点分为三类
1.没有被访问到的点。这类点被标记0
2.正处于dfs阶段，即没有经过回溯的点，这类点给标记1
3.已经结束dfs阶段，即已经回溯结束的点，这类点给标记2
每次一个点结束dfs阶段，就将其标记位2，并将这个点合并到其父亲所在的并查集中（可以保证其父亲此时的标记一定1），
当其他点有问题边连到该点时，这个问题的解就是其所在并查集的标号
比较形象化的理解，在dfs过程中，x,y结点的lca必定是其路径上深度最小的结点，而深度最小的结点在dfs访问到y时一定没有被回溯，并且此时x已经被回溯了，被归并在lca所在的集合中，
那么扫描和y有关的所有问题，如果另一个点已经被标记位2，说明y和这个点已经相遇过了，相遇的点就是这个点所在的并查集标号
那么就使用并查集来优化这个集合的合并即可。
//多次求树上两点之间的距离
vector<int>q[maxn],q_id[maxn];//查询链表
int v[maxn],f[maxn],ans[maxn];//标记数组,并查集
void tarjan(int x){
v[x]=;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to
if(v[y])continue;
d[y]=d[x]+edge[i].w;//求y的深度
tarjan(y);
f[y]=x;//回溯后将y并入x集合中
}
for(int i=;i<q[x].size();i++){
int y=q[x][i],id=q_id[x][i];
if(v[y]==){//y是已经回溯过的结点
int lca=find(y);//使用并查集求y的集合标记
ans[id]=min(ans[id],d[x]+d[y]-*d[lca]);
}
}
v[x]=;//x回溯完成了
}