https://www.luogu.org/problemnew/show/P3379 题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。 接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式： 输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例 输入样例#1： 5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 输出样例#1： 4 4 1 4 4 说明 时空限制：1000ms,128M 数据规模： 对于30%的数据：N<=10，M<=10 对于70%的数据：N<=10000，M<=10000 对于100%的数据：N<=500000，M<=500000
核心代码
void dfs(int u,int fa) O(n) { f[u][0]=fa; for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].v; if(v==fa) continue; dep[v]=dep[u]+1; dfs(v,u); } } int lca(int x,int y)// O(1) { if(dep[x]<dep[y]) swap(dep[x],dep[y]); for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; }ALL
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<cstdlib> #include<ctime> #define N 500010 using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; inline int read(){ char ch=' ';int f=1;int x=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } int to[N*2],next1[N*2],h[N],f[N][25],dep[N],si,s,n,m; void Add(int u,int v) { to[++si]=v;next1[si]=h[u];h[u]=si; } void dfs(int a,int fa) { f[a][0]=fa; for(int i=1;i<=20;i++) f[a][i]=f[f[a][i-1]][i-1]; for(int i=h[a];i;i=next1[i]) { int y=to[i]; if(y==fa) continue; dep[y]=dep[a]+1; dfs(y,a); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); Add(u,v);Add(v,u); } dep[s]=1; dfs(s,0); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } }