（题目总结）LCA板子以及一些题目
LCA算法总结
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
把lca题目记入下来！分享给你们
板子tarjan（离线）
#define N 10005 #define M 1000005 // N 表示的树的节点 // M 表示的问题数 int cnt_e,cnt_q,head_e[N],head_q[N],vis[N],dis[N],t,ans[M],id[N],f[N]; // 边，问题数 struct node{ int u,w,next; }e[N*2],q[M*2]; void init(){ memset(head_e,-1,sizeof(head_e)); memset(head_q,-1,sizeof(head_q)); memset(vis,0,sizeof(vis)); cnt_e=0; cnt_q=0; } void addedge(int x,int y,int z){ e[cnt_e].u=x;e[cnt_e].w=z;e[cnt_e].next=head_e[y];head_e[y]=cnt_e++; e[cnt_e].u=y;e[cnt_e].w=z;e[cnt_e].next=head_e[x];head_e[x]=cnt_e++; } void addquery(int x,int y,int z){ q[cnt_q].u=x;q[cnt_q].w=z;q[cnt_q].next=head_q[y];head_q[y]=cnt_q++; q[cnt_q].u=y;q[cnt_q].w=z;q[cnt_q].next=head_q[x];head_q[x]=cnt_q++; } int find(int x){ if(f[x] == x) return x; else return f[x] = find(f[x]); } void tarjan(int k){ f[k]=k; vis[k]=1; id[k]=t; int i,v; for(i=head_q[k];i!=-1;i=q[i].next){ v=q[i].u; if(vis[v]){ // 表示的就是一颗树 // 每次只需要在这里做文章就行 // ans[q[i].w] = find(v); //求的是lca //ans[q[i].w]=dis[k]+dis[v]-2*dis[find(v)]; //求的是两个点的距离 // solve1() 可以表示的是森林 //可以去求这个森林 if(id[v] == id[k]) //ans[q[i].w] = find(v); ans[q[i].w] = dis[k]+dis[v]-2*dis[find(v)]; else ans[q[i].w]=-1; } } for(i=head_e[k];i!=-1;i=e[i].next){ v=e[i].u; if(!vis[v]){ dis[v]=dis[k]+e[i].w; tarjan(v); f[v]=k; } } }View Code
LCA第一题：
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先
我的理解：
直接套板子（因为是一颗树！直接套solve2）
AC 代码
#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<string> #include<set> typedef long long int ll; using namespace std; void read(int &x){ int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } #define N 500005 #define M 1000005 // N 表示的树的节点 // M 表示的问题数 int cnt_e,cnt_q,head_e[N],head_q[N],vis[N],dis[N],t,ans[M],id[N],f[N]; // 边，问题数 struct node{ int u,w,next; }e[N*2],q[M*2]; void init(){ memset(head_e,-1,sizeof(head_e)); memset(head_q,-1,sizeof(head_q)); memset(vis,0,sizeof(vis)); cnt_e=0; cnt_q=0; } void addedge(int x,int y,int z){ e[cnt_e].u=x;e[cnt_e].w=z;e[cnt_e].next=head_e[y];head_e[y]=cnt_e++; e[cnt_e].u=y;e[cnt_e].w=z;e[cnt_e].next=head_e[x];head_e[x]=cnt_e++; } void addquery(int x,int y,int z){ q[cnt_q].u=x;q[cnt_q].w=z;q[cnt_q].next=head_q[y];head_q[y]=cnt_q++; q[cnt_q].u=y;q[cnt_q].w=z;q[cnt_q].next=head_q[x];head_q[x]=cnt_q++; } int find(int x){ if(f[x] == x) return x; else return f[x] = find(f[x]); } void tarjan(int k){ f[k]=k; vis[k]=1; id[k]=t; int i,v; for(i=head_q[k];i!=-1;i=q[i].next){ v=q[i].u; if(vis[v]){ // 表示的就是一颗树 // 每次只需要在这里做文章就行 ans[q[i].w] = find(v); //求的是lca //ans[q[i].w]=dis[k]+dis[v]-2*dis[find(v)]; //求的是两个点的距离 // solve1() 可以表示的是森林 //可以去求这个森林 /* //ans[q[i].w] = find(v); ans[q[i].w] = dis[k]+dis[v]-2*dis[find(v)]; else ans[q[i].w]=-1; */ } } for(i=head_e[k];i!=-1;i=e[i].next){ v=e[i].u; if(!vis[v]){ dis[v]=dis[k]+e[i].w; tarjan(v); f[v]=k; } } } void solve1(){ int n, m, cc, root, x, y, z; while(scanf("%d%d%d",&n,&cc,&m) == 3){ init(); while(cc--){ //scanf("%d%d%d",&x,&y,&z); read(x),read(y),read(z); //z = 1; addedge(x,y,z); } for(int i = 0;i < m; i++){ read(x),read(y); //scanf("%d%d",&x,&y); addquery(x,y,i); } t = 0; // 这个是全局的变量 for(int i = 1; i <= n; i++, t++){ if(!vis[i]){ dis[i] = 0; tarjan(i); } } for(int i = 0; i < m; i++){ if(ans[i] == -1){ // 表示的就是不在一颗树 puts("Not connected"); }else printf("%d\n",ans[i]); } } } void solve2(){ // 需要注意的就是这个tarjan 里面ans换下就可以求一颗树 int tt ; //read(tt); tt = 1; while(tt--){ int n, m, cc, root, x, y, z; read(n),read(m),read(root); init(); for(int i = 1; i < n; i++){ read(x),read(y); //read(z); z = 1; //scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } for(int i = 0; i < m; i++){ read(x),read(y); addquery(x,y,i); } // 一颗树的话，一般root 为1 ///只有一颗树，t 默认为0 // root = 1; t = 0; dis[root] = 0; tarjan(root); for(int i = 0; i < m; i++){ printf("%d\n",ans[i]); } } } int main(){ int tt; //read(tt); tt = 1; while(tt--){ // 1 表示的就是森林 //solve1(); solve2(); } return 0; }AC
LCA第二题
题意：给你n个点！然后就是这些树构成一个森林！求两个点的距离！要是不在同一颗树就输入题目条件
理解：离线tarjan！查询次数太多了！所以离线不容易TLE！还有卡常数
#include<bits/stdc++.h> typedef long long int ll; using namespace std; void read(int &x){ int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } #define N 10005 #define M 1000005 // N 表示的树的节点 // M 表示的问题数 int cnt_e,cnt_q,head_e[N],head_q[N],vis[N],dis[N],t,ans[M],id[N],f[N]; // 边，问题数 struct node{ int u,w,next; }e[N*2],q[M*2]; void init(){ memset(head_e,-1,sizeof(head_e)); memset(head_q,-1,sizeof(head_q)); memset(vis,0,sizeof(vis)); cnt_e=0; cnt_q=0; } void addedge(int x,int y,int z){ e[cnt_e].u=x;e[cnt_e].w=z;e[cnt_e].next=head_e[y];head_e[y]=cnt_e++; e[cnt_e].u=y;e[cnt_e].w=z;e[cnt_e].next=head_e[x];head_e[x]=cnt_e++; } void addquery(int x,int y,int z){ q[cnt_q].u=x;q[cnt_q].w=z;q[cnt_q].next=head_q[y];head_q[y]=cnt_q++; q[cnt_q].u=y;q[cnt_q].w=z;q[cnt_q].next=head_q[x];head_q[x]=cnt_q++; } int find(int x){ if(f[x] == x) return x; else return f[x] = find(f[x]); } void tarjan(int k){ f[k]=k; vis[k]=1; id[k]=t; int i,v; for(i=head_q[k];i!=-1;i=q[i].next){ v=q[i].u; if(vis[v]){ // 表示的就是一颗树 // 每次只需要在这里做文章就行 //ans[q[i].w] = find(v); //求的是lca //ans[q[i].w]=dis[k]+dis[v]-2*dis[find(v)]; //求的是两个点的距离 // solve1() 可以表示的是森林 //可以去求这个森林 //ans[q[i].w] = find(v); if(id[v] == id[k]) ans[q[i].w] = dis[k]+dis[v]-2*dis[find(v)]; else ans[q[i].w]=-1; } } for(i=head_e[k];i!=-1;i=e[i].next){ v=e[i].u; if(!vis[v]){ dis[v]=dis[k]+e[i].w; tarjan(v); f[v]=k; } } } void solve1(){ int n, m, cc, root, x, y, z; while(scanf("%d%d%d",&n,&cc,&m) == 3){ init(); while(cc--){ //scanf("%d%d%d",&x,&y,&z); read(x),read(y),read(z); //z = 1; addedge(x,y,z); } for(int i = 0;i < m; i++){ read(x),read(y); //scanf("%d%d",&x,&y); addquery(x,y,i); } t = 0; // 这个是全局的变量 for(int i = 1; i <= n; i++, t++){ if(!vis[i]){ dis[i] = 0; tarjan(i); } } for(int i = 0; i < m; i++){ if(ans[i] == -1){ // 表示的就是不在一颗树 puts("Not connected"); }else printf("%d\n",ans[i]); } } } void solve2(){ // 需要注意的就是这个tarjan 里面ans换下就可以求一颗树 int tt ; //read(tt); tt = 1; while(tt--){ int n, m, cc, root, x, y, z; read(n),read(m),read(root); init(); for(int i = 1; i < n; i++){ read(x),read(y); //read(z); z = 1; //scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } for(int i = 0; i < m; i++){ read(x),read(y); addquery(x,y,i); } // 一颗树的话，一般root 为1 ///只有一颗树，t 默认为0 // root = 1; t = 0; dis[root] = 0; tarjan(root); for(int i = 0; i < m; i++){ printf("%d\n",ans[i]); } } } int main(){ int tt; //read(tt); tt = 1; while(tt--){ // 1 表示的就是森林 solve1(); //solve2(); } return 0; }AC代码
持续更新中
更多精彩
