![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/10\/20261029100856-6ae31b38d925b.png\")
<\/p>\n\u00a0 \u00a0 \u00a0 \u00a0 LCA\u7b97\u6cd5\u662f\u4e00\u79cd\u6c42\u6811\u4e0a\u6700\u8fd1\u516c\u5171\u7956\u5148\u7684\u7b97\u6cd5\u3002<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u6700\u8fd1\u516c\u5171\u7956\u5148：\u4e24\u4e2a\u8282\u70b9\u5728\u6811\u4e2d\u6df1\u5ea6\u6700\u5927\u7684\u5171\u540c\u7956\u5148\u8282\u70b9\u3002<\/p>\n
<\/p>\n
\u4f8b\u5982：\u8282\u70b91\u548c\u8282\u70b95\u7684\u516c\u5171\u7956\u5148\u67094\u30017，\u6700\u8fd1\u516c\u5171\u7956\u5148\u662f4\u3002<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u8282\u70b95\u548c\u8282\u70b98\u7684\u516c\u5171\u7956\u5148\u67097，\u6700\u8fd1\u516c\u5171\u7956\u5148\u662f7\u3002<\/p>\n
\u6838\u5fc3<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u5b9e\u73b0LCA\u7b97\u6cd5\u9700\u8981\u5148\u901a\u8fc7\u500d\u589e\u7684\u65b9\u6cd5\u6c42\u51fa\u6570\u7ec4f[i][j]（f[i][j]\u8868\u793a\u4ece\u8282\u70b9i\u5411\u4e0a\u8df3\u7684\u7b2c2^j\u4e2a\u7956\u5148\u8282\u70b9\u7684\u7f16\u53f7）\u3002\u7136\u540eLCA\u7b97\u6cd5\u7684\u6838\u5fc3\u662f\u4e00\u4e2a\u70b9\u5148\u8df3，\u8ba9\u540e\u4e00\u8d77\u8df3\u3002<\/p>\n
\u4f8b\u9898：\u7ed9\u5b9a\u4e00\u9897n\u4e2a\u8282\u70b9\u7684\u6811，m\u6b21\u8be2\u95ee，\u6bcf\u6b21\u8be2\u95eex,y\u6c42\u5b83\u4eec\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148\u3002<\/p>\n
#include<bits\/stdc++.h>
\nusing namespace std;
\nconst int N=5E5+10,L=20;
\nvector<int> a[N];
\nint dep[N];\/\/\u8282\u70b9\u7684\u6df1\u5ea6
\nint f[N][L];\/\/\u8282\u70b9i\u5411\u4e0a\u8df3\u7684\u7b2c2^j\u4e2a\u7956\u5148\u8282\u70b9\u7684\u7f16\u53f7
\nint lg[N];\/\/log2(i) <\/p>\n
\/\/\u521d\u59cb\u5316dfs
\nvoid dfs(int x,int fath){
\nf[x][0]=fath;\/\/\u5411\u4e0a\u8df31\u5c42\u662f\u7236\u4eb2
\ndep[x]=dep[fath]+1;
\nfor(int i=0;i<a[x].size();i++){
\nint y=a[x][i];
\nif(y!=fath)dfs(y,x);
\n}
\n}<\/p>\n
\/\/\u7ecf\u5178\u7684lowbit\u51fd\u6570,\u6c42\u4e8c\u8fdb\u5236\u4e2d\u6700\u4f4e\u4f4d\u76841
\nint lowbit(int x){
\nreturn x&-x;
\n}<\/p>\n
\/\/\u6c42\u6700\u8fd1\u516c\u5171\u7956\u5148
\nint lca(int x,int y){
\nif(dep[x]<dep[y])swap(x,y);\/\/x\u6df1\u5ea6\u8981\u5927\u4e8ey <\/p>\n
\/\/x\u5148\u8df3\u5230\u548cy\u540c\u6837\u6df1\u5ea6\u7684\u4f4d\u7f6e
\nint t=dep[x]-dep[y];
\nwhile(t){
\nint lt=lowbit(t);
\nt-=lt;
\nx=f[x][lg[lt]];
\n}
\nif(x==y)return x;\/\/\u7279\u5224 <\/p>\n
\/\/x，y\u4e00\u8d77\u5411\u4e0a\u8df3\u76f8\u540c\u7684\u9ad8\u5ea6\u8fc7\u7a0b\u4e2dx!=y
\nfor(int i=L-1;i>=0;i–){\/\/\u5012\u7740\u5faa\u73af！
\nif(f[x][i]!=f[y][i]){
\nx=f[x][i];
\ny=f[y][i];
\n}
\n}
\nreturn f[x][0];\/\/\u5b83\u4eec\u7684\u7236\u4eb2\u662f\u7b54\u6848
\n}<\/p>\n
int main(){
\nint n,m,s;
\ncin>>n>>m>>s;
\nfor(int i=1;i<n;i++){
\nint x,y;
\nscanf("%d%d",&x,&y);
\na[x].push_back(y);
\na[y].push_back(x);
\n}<\/p>\n
dfs(s,0);<\/p>\n
\/\/\u500d\u589e\u6c42f
\nfor(int j=1;j<L;j++){
\nfor(int i=1;i<=n;i++){
\nf[i][j]=f[f[i][j-1]][j-1];
\n}
\n}<\/p>\n
lg[1]=0;\/\/\u4ece2\u5f00\u59cb！
\nfor(int i=2;i<=n;i++)lg[i]=lg[i\/2]+1;<\/p>\n
while(m–){
\nint x,y;
\nscanf("%d%d",&x,&y);
\nprintf("%d\\\\n",lca(x,y));
\n}<\/p>\n
return 0;
\n}<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0LCA\u9884\u5904\u7406O(nlogn)，\u67e5\u8be2O(mlogn)，\u5e94\u7528\u7279\u522b\u5e7f\u3002<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u8c22\u8c22\u89c2\u770b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
LCA\u7b97\u6cd5\u662f\u4e00\u79cd\u6c42\u6811\u4e0a\u6700\u8fd1\u516c\u5171\u7956\u5148\u7684\u7b97\u6cd5\u3002\u6700\u8fd1\u516c\u5171\u7956\u5148：\u4e24\u4e2a\u8282\u70b9\u5728\u6811\u4e2d\u6df1\u5ea6\u6700\u5927\u7684\u5171\u540c\u7956\u5148\u8282\u70b9\u3002\u4f8b\u5982：\u8282\u70b91\u548c\u8282\u70b95\u7684\u516c\u5171\u7956\u5148\u67094\u30017，\u6700\u8fd1\u516c\u5171\u7956\u5148\u662f4\u3002\u8282\u70b95\u548c\u8282\u70b98\u7684\u516c\u5171\u7956\u5148\u67097，\u6700\u8fd1\u516c\u5171\u7956\u5148\u662f7\u3002\u6838\u5fc3\u5b9e\u73b0LCA\u7b97\u6cd5\u9700\u8981\u5148\u901a\u8fc7\u500d\u589e\u7684\u65b9\u6cd5\u6c42\u51fa\u6570\u7ec4f[i][j]（f[i][j]\u8868\u793a\u4ece\u8282\u70b9i\u5411\u4e0a\u8df3\u7684\u7b2c2^j\u4e2a\u7956\u5148\u8282\u70b9\u7684\u7f16\u53f7）\u3002\u7136\u540eLCA\u7b97\u6cd5\u7684\u6838\u5fc3\u662f\u4e00\u4e2a\u70b9\u5148\u8df3，\u8ba9\u540e\u4e00\u8d77\u8df3\u3002\u4f8b\u9898<\/p>\n","protected":false},"author":2,"featured_media":119453,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[13617,13618,55,1982,427],"topic":[],"class_list":["post-119454","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-lca","tag-13618","tag-c","tag-1982","tag-427"],"yoast_head":"\n