首页 > 代码库 > LCA 笔记
LCA 笔记
简述这几天的LCA 心得：
LCA有两种做法：离线 or 在线
先学的离线；
原理博客很多。
我写得两道题，已经模板。
HDU:http://acm.hdu.edu.cn/showproblem.php?pid=2586
HDU :http://acm.hdu.edu.cn/showproblem.php?pid=2874 2874;
之前一份板子：
1 #pragma comment(linker, "/STACK:10240000000,10240000000") 2 3 #include<iostream> 4 #include<stdio.h> 5 #include<string.h> 6 #include<cmath> 7 #include<algorithm> 8 #include<string> 9 #include<vector>10 using namespace std;11 12 #define N 5111113 struct node14 {15 int v,w;16 17 node(int vv,int ww)18 {19 v=vv;20 w=ww;21 }22 };23 int f[N],dis[N],ans[N],vis[N],n;24 vector<node>mp[N];25 vector<node>q[N];26 27 int find(int x)28 {29 if (f[x]!=x) f[x]=find(f[x]);30 return f[x];31 }32 33 void lca(int u)34 {35 for (int i=0;i<mp[u].size();i++)36 {37 int v=mp[u][i].v;38 if (vis[v]) continue;39 vis[v]=1;40 41 dis[v]=dis[u]+mp[u][i].w;42 lca(v);43 f[v]=u;44 for (int j=0;j<q[v].size();j++)45 {46 int c=q[v][j].v;47 if (vis[c]&&ans[q[v][j].w]==-1)48 {49 if (v==c) ans[q[v][j].w]=0;50 else ans[q[v][j].w]=dis[v]+dis[c]-2*dis[find(c)];51 }52 }53 }54 }55 56 int main()57 {58 int T;59 scanf("%d",&T);60 while (T--)61 {62 int m;63 scanf("%d%d",&n,&m);64 for (int i=1;i<=n;i++)65 {66 mp[i].clear();67 q[i].clear();68 ans[i]=-1;69 f[i]=i;70 vis[i]=0;71 }72 for (int i=1;i<n;i++)73 {74 int a,b,c;75 scanf("%d%d%d",&a,&b,&c);76 mp[a].push_back(node(b,c));77 mp[b].push_back(node(a,c));78 }79 for (int i=1;i<=m;i++)80 {81 int a,b;82 scanf("%d%d",&a,&b);83 q[a].push_back(node(b,i));84 q[b].push_back(node(a,i));85 }86 vis[1]=1;87 dis[1]=0;88 lca(1);89 90 for (int i=1;i<=m;i++)91 printf("%d\n",ans[i]);92 }93 return 0;94 }
是有问题的，但是数据弱所以没爆出来。
正确形式：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<cmath> 5 #include<algorithm> 6 #include<string> 7 #include<vector> 8 using namespace std; 9 10 #define N 5111111 struct node12 {13 int v,w;14 15 node(int vv,int ww)16 {17 v=vv;18 w=ww;19 }20 };21 int f[N],dis[N],ans[N],vis[N],n;22 vector<node>mp[N];23 vector<node>q[N];24 25 int find(int x)26 {27 if (f[x]!=x) f[x]=find(f[x]);28 return f[x];29 }30 31 void lca(int u)32 {33 for (int i=0;i<mp[u].size();i++)34 {35 int v=mp[u][i].v;36 if (vis[v]) continue;37 vis[v]=1;38 39 dis[v]=dis[u]+mp[u][i].w;40 lca(v);41 f[v]=u;42 }43 for (int j=0;j<q[u].size();j++)44 {45 int c=q[u][j].v;46 if (vis[c]&&ans[q[u][j].w]==-1)47 {48 if (u==c) ans[q[u][j].w]=0;49 else ans[q[u][j].w]=dis[u]+dis[c]-2*dis[find(c)];50 }51 }52 53 }54 55 int main()56 {57 int T;58 scanf("%d",&T);59 while (T--)60 {61 int m;62 scanf("%d%d",&n,&m);63 for (int i=1;i<=n;i++)64 {65 mp[i].clear();66 q[i].clear();67 ans[i]=-1;68 f[i]=i;69 vis[i]=0;70 }71 for (int i=1;i<n;i++)72 {73 int a,b,c;74 scanf("%d%d%d",&a,&b,&c);75 mp[a].push_back(node(b,c));76 mp[b].push_back(node(a,c));77 }78 for (int i=1;i<=m;i++)79 {80 int a,b;81 scanf("%d%d",&a,&b);82 q[a].push_back(node(b,i));83 q[b].push_back(node(a,i));84 }85 vis[1]=1;86 dis[1]=0;87 lca(1);88 89 for (int i=1;i<=m;i++)90 printf("%d\n",ans[i]);91 }92 return 0;93 }
可以仔细体验差别。
因为 在其中吃了大亏。HDU 2874 （都是简单题）卡了三天 。想想算法没错 ，果然是板子的问题。
换一种写法也可以，询问在递归前面也可以。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<cmath> 5 #include<algorithm> 6 #include<string> 7 #include<vector> 8 using namespace std; 9 10 #define N 21111 11 typedef long long ll; 12 struct node 13 { 14 int v,w; 15 node(int vv=0,int ww=0) 16 { 17 v=vv; 18 w=ww; 19 } 20 }; 21 22 int f[N]; 23 int ans[1110000],dis[N]; 24 int vis[N],mark[N]; 25 26 vector<node>mp[N]; 27 vector<node>q[N]; 28 29 int find(int x) 30 { 31 if (f[x]!=x) f[x]=find(f[x]); 32 return f[x]; 33 } 34 35 void lca(int u) 36 { 37 38 for (int i=0;i<q[u].size();i++) 39 { 40 int c=q[u][i].v; 41 int w=q[u][i].w; 42 if (vis[c]&&ans[w]==-1&&mark[find(c)]!=1) 43 { 44 ans[w]=dis[u]+dis[c]-2*dis[find(c)]; 45 } 46 } 47 48 for (int i=0;i<mp[u].size();i++) 49 { 50 int v=mp[u][i].v; 51 if (vis[v]) continue; 52 vis[v]=1; 53 dis[v]=dis[u]+mp[u][i].w; 54 lca(v); 55 f[v]=u; 56 /* 57 for (int j=0;j<q[v].size();j++) 58 { 59 int c=q[v][j].v; 60 int w=q[v][j].w; 61 if (vis[c]&&ans[w]==-1&&mark[find(c)]!=1) 62 { 63 // if (v==c) ans[w]=0; 64 // else 65 ans[w]=dis[v]+dis[c]-2*dis[find(c)]; 66 } 67 } 68 */ 69 70 } 71 } 72 73 int main() 74 { 75 // freopen("input.txt","r",stdin); 76 // freopen("output1.txt","w",stdout); 77 int n,m,C; 78 while (scanf("%d%d%d",&n,&m,&C)!=EOF) 79 { 80 for (int i=0;i<=n;i++) 81 { 82 f[i]=i; 83 mp[i].clear(); 84 q[i].clear(); 85 vis[i]=0; 86 dis[i]=0; 87 mark[i]=0; 88 } 89 for (int i=1;i<=C;i++) ans[i]=-1; 90 for (int i=1;i<=m;i++) 91 { 92 int a,b,c; 93 scanf("%d%d%d",&a,&b,&c); 94 mp[a].push_back(node(b,c)); 95 mp[b].push_back(node(a,c)); 96 } 97 for (int i=1;i<=C;i++) 98 { 99 int a,b;100 scanf("%d%d",&a,&b);101 q[a].push_back(node(b,i));102 q[b].push_back(node(a,i));103 }104 105 for (int i=1;i<=n;i++)106 if (!vis[i])107 {108 vis[i]=1;109 dis[i]=0;110 lca(i);111 mark[i]=1;112 }113 114 for (int i=1;i<=n;i++)115 for (int j=0;j<q[i].size();j++)116 {117 int u=i;118 int v=q[i][j].v;119 int w=q[i][j].w;120 if (find(u)!=find(v)) ans[w]=-1;121 }122 123 124 for (int i=1;i<=C;i++)125 if (ans[i]==-1) printf("Not connected\n");126 else printf("%d\n",ans[i]);127 128 }129 return 0;130 }
LCA 笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。