题目传送门
诶，自己真的是越来越菜了，自己寒假里学会的LCA到现在已经忘得差不多了。
今天就当是复习一下吧。
其实这个倍增的思想还是挺神奇的，每次询问时先把深度较大的节点倍增到和深度较小的节点同一深度。
然后再把这两个节点同时倍增到离它们最远的不相同的祖先出，赋值并循环，最后返回当前任意一个节点的父亲节点就是这两个节点的LCA了。
附上AC代码：
#include <cstdio> #include <cctype> #include <cmath> #include <algorithm> #define N 500010 using namespace std; struct side{ int to,nt; }s[N<<1]; int n,m,st,x,y,num,h[N],d[N],f[N][21],k; bool b[N]; inline char nc(){ static char ch[100010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(int &a){ static char c=nc();int f=1; for (;!isdigit(c);c=nc()) if (c=='-') f=-1; for (a=0;isdigit(c);a=a*10+c-'0',c=nc()); a*=f;return; } inline void add(int x,int y){ s[++num]=(side){y,h[x]},h[x]=num; s[++num]=(side){x,h[y]},h[y]=num; } inline void build(int x){ b[x]=1; for (int i=h[x]; i; i=s[i].nt) if (!b[s[i].to]) d[s[i].to]=d[x]+1,f[s[i].to][0]=x,build(s[i].to); return; } inline int query(int x,int y){ if (d[x]<d[y]) swap(x,y); for (int i=k; i>=0; --i) if (d[f[x][i]]>=d[y]) x=f[x][i]; if (x==y) return x; for (int i=k; i>=0; --i) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int main(void){ read(n),read(m),read(st); for (int i=1; i<n; ++i) read(x),read(y),add(x,y); d[st]=1,build(st),k=log(n)/log(2)+1; for (int j=1; j<=k; ++j) for (int i=1; i<=n; ++i) f[i][j]=f[f[i][j-1]][j-1]; for (int i=1; i<=m; ++i){ read(x),read(y); printf("%d\n",query(x,y)); } return 0; }