今天继续学习LCA，今天学的方法是倍增。
倍增的思路非常简单：
1.用dfs求出每个节点的深度。
2.若查询的u,v不在同一深度，则将深度深的节点的深度更新至深度浅的节点的深度（就是将深度深的节点更新成它的父节点）。
3.判断两个节点是否重合，若不重合，都更新成父节点，直至重合，这个节点就是u,v的最近公共祖先。
但是运行出来会很慢，所以就需要优化：
这里需要用到st表，存一个节点的向上找2^j次的祖宗，即是倍增，每次向上更新2^j比一次一次向上更新快。
下面是代码：
#include<iostream> #include<cmath> using namespace std; int read(){ int x=0,f=1; char a=getchar(); while(a<'0'||a>'9'){ if(a=='-')f=-1; a=getchar(); } while(a>='0'&&a<='9'){ x*=10; x+=a-'0'; a=getchar(); } return x*f; } int n,m,s; int head[500010],tot; int h[500010]; int vis[500010],f[500010][20],lg[500010]; struct node{ int to; int nxt; }edge[1000010]; void build(int u,int v){ edge[++tot].to=v; edge[tot].nxt=head[u]; head[u]=tot; } void dfs(int u){ for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(vis[v]==0){ vis[v]=1; h[v]=h[u]+1; f[v][0]=u; for(int i=1;i<log2(h[v]);i++){ f[v][i]=f[f[v][i-1]][i-1]; } dfs(v); } } } int main(){ n=read();m=read();s=read(); for(int i=1;i<n;i++){ int u,v; u=read();v=read(); build(u,v); build(v,u); } for(int i=1;i<=n;i++){ lg[i]=lg[i-1]+(1<<lg[i-1]==i); } vis[s]=1; f[s][0]=s; h[s]=1; dfs(s); for(int i=1;i<=m;i++){ int u,v; u=read();v=read(); while(h[u]<h[v]){ v=f[v][lg[h[v]-h[u]]-1]; } while(h[u]>h[v]){ u=f[u][lg[h[u]-h[v]]-1]; } for(int j=log2(h[v]);j>=0;j--){ if(f[u][j]!=f[v][j]){ u=f[u][j]; v=f[v][j]; } } while(u!=v){ u=f[u][0]; v=f[v][0]; } printf("%d\n",v); } return 0; }