LCA
任意两点U,V的最近公共祖先即为LCA
树上倍增O（(n+m)*logn）
思想：使用二进制来实现大幅度的空间跳跃。
初始化F[][]数组为0或者-1，F[i][j]表示节点i的第2^j位祖先，进行倍增的时候可以使用F[i][j] = F[ F[i][j-1] ][j-1]来处理节点i的所有祖先节点
Code：
F[][]：记录节点的祖先集
dep[]：记录节点的深度
vis[]：记录节点的访问信息
to[]，head[]，next[]：存储节点信息
add()：存储节点
BFS()：处理节点信息
LCA()：查找最近公共祖先
void add(int u,int v){to[cnt] = v ; next[cnt] = head[u] ; head[u] = cnt++;}
void BFS()
{
queue<int>q;
q.push(1); dep[1] = 1 ;
while(!q.empty()){
int u = q.front() ; q.pop() ;
for(int i=head[u];~i/*i*/;i=next[i]){
int v = to[i] ;
if(dep[v]) continue;
dep[v] = dep[u] + 1 ; F[v][0] = u ;
for(int j=1;j<=lg2;j++)
F[v][j] = F[ F[v][j-1] ][j-1] ;
q.push(v);
}
}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
for(int i=lg2;i>=0;i--){
if(dep[ F[v][i] ]>=dep[u])
v = F[v][i] ;
}
if(u==v) return u;
for(int i=lg2;i>=0;i--){
if(F[u][i]!=F[v][i])
u = F[u][i] , v = F[v][i] ;
}
return F[u][0];
}
void init()
{
lg2 = log2(n) + 1 ;/// 全局变量
memset(head,-1,sizeof(head));
}
void solve()
{
read(n) , read(m) ; init() ;
for(int i=1 , u , v ;i<=n;i++){
read(u) , read(v) ;
add(u,v) ; add(v,u);
}
BFS();
while(m--){
int u,v;
read(u) ; read(v) ;
printf("%d\n",LCA(u,v));
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
Tarjan O(n+m)
思想：每次处理完一颗子树，将子树合并到其父节点集合中上，也就是并查集优化
通过记录DFS遍历是否回溯来离线处理查询，初始vis[]为0，遍历为1，回溯为2.
vector< pair<int,int> > q[mxn];
void add(int u,int v){to[cnt] = v ; next[cnt] = head[u] ; head[u] = cnt++;}
int Find(int x){return x==pre[x]?x:pre[x] = Find(pre[x]);}
void add(int u,int v,int id){q[u].push_back({v,id});q[v].push_back({u,id});}
void Tarjan(int u)
{
vis[u] = 1 ;
for(int i=head[u];~i;i=next[i]){
int v = to[i] ;
if(vis[v]) continue;
Tarjan(v);
pre[v] = u ;
}
for(auto i:q[u]){
int v = i.first , id = i.second ;
if(vis[v]==2) ans[id] = Find(v);
}
vis[u] = 2 ;
}
void init()
{
cnt = 0 ; res = 0 ;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) pre[i] = i ;
}
void solve()
{
read(n) , read(m) ; init() ;
for(int i=1 , u , v ;i<=n;i++){
read(u) , read(v) ;
add(u,v) ; add(v,u);
}
for(int i=1,u,v;i<=m;i++){
read(u) , read(v) ;
add(u,v,i); add(v,u,i);
}
Tarjan(1);
for(int i=1;i<=m;i++){
printf("%d\n", ans[i]);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
