洛谷 P3379 【模板】最近公共祖先（LCA） (在线倍增+离线Tarjan)

本文主要是介绍洛谷 P3379 【模板】最近公共祖先（LCA） (在线倍增+离线Tarjan)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式：

第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式：

输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

输入样例#1：

输出样例#1：

思路

题如其名，就是lca的模板。我就存一存我的lca模板~

离线Tarjan

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;
int pre[N],first[N],first2[N],tot,tot2;
bool vis[N];//标记有没有询问
int n;
struct edge
{int v,next;
} e[2*N];
struct Query
{int v,w,next;
} query[2*N];void add_edge(int u,int v)
{e[tot].v=v;e[tot].next=first[u];first[u]=tot++;
}void add_query(int u,int v)
{query[tot2].v=v;query[tot2].w=-1;query[tot2].next=first2[u];first2[u]=tot2++;
}int find(int x)
{return x==pre[x]?x:pre[x]=find(pre[x]);
}int lca(int u,int fa)
{for(int i=first[u]; ~i; i=e[i].next){int v=e[i].v;if(v==fa) continue;lca(v,u);pre[v]=u;}vis[u]=1;for(int i=first2[u]; ~i; i=query[i].next){int v=query[i].v;if(vis[v])query[i].w=find(v);}
}void init()
{mem(first,-1);mem(first2,-1);mem(vis,0);tot=0;tot2=0;for(int i=1; i<=n; i++)pre[i]=i;
}int main()
{int m,s,u,v;scanf("%d%d%d",&n,&m,&s);init();for(int i=1; i<n; i++){scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}for(int i=1; i<=m; i++){scanf("%d%d",&u,&v);add_query(u,v);add_query(v,u);}lca(s,pre[s]);for(int i=0; i<tot2; i++)if(query[i].w!=-1)printf("%d\n",query[i].w);return 0;
}

在线倍增

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;int n,m,s;
int tot;
int first[N],d[N],p[N][21];struct edge
{int v,next;
} e[2*N];void add_edge(int u,int v)
{e[tot].v=v;e[tot].next=first[u];first[u]=tot++;
}void dfs(int u,int fa)
{d[u]=d[fa]+1;p[u][0]=fa;for(int i=1; (1<<i)<=d[u]; i++)p[u][i]=p[p[u][i-1]][i-1];for(int i=first[u]; ~i; i=e[i].next){int v=e[i].v;if(v!=fa)dfs(v,u);}
}int lca(int a,int b)
{if(d[a]>d[b]) swap(a,b);//保证a在b点的上方for(int i=20; i>=0; i--)if(d[a]<=d[b]-(1<<i))b=p[b][i];  //把b移到和a同一个深度if(a==b) return a;for(int i=20; i>=0; i--){if(p[a][i]==p[b][i])continue;elsea=p[a][i],b=p[b][i];//一起向上跳跃}return p[a][0];
}void init()
{tot=0;mem(first,-1);mem(d,0);mem(p,0);
}
int main()
{init();int a,b;scanf("%d%d%d",&n,&m,&s);for(int i=1; i<n; i++){scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}dfs(s,0);for(int i=1; i<=m; i++){scanf("%d%d",&a,&b);printf("%d\n",lca(a,b));}return 0;
}