关键词：
倍增lca板子洛谷P3379
1 #include<cstdio> 2 struct E 3 { 4 int to,next; 5 }e[1001000]; 6 int f1[500100],anc[500100][20],log2n,deep[500100],n,m,s,ne; 7 bool vis[500100]; 8 void dfs(int x,int fa) 9 { 10 int i,k; 11 vis[x]=1; 12 anc[x][0]=fa; 13 deep[x]=deep[fa]+1; 14 for(i=1;i<=log2n;i++) 15 anc[x][i]=anc[anc[x][i-1]][i-1]; 16 for(k=f1[x];k!=0;k=e[k].next) 17 if(!vis[e[k].to]) 18 dfs(e[k].to,x); 19 } 20 int lca(int x,int y) 21 { 22 int t,i; 23 if(deep[x]<deep[y]){t=x;x=y;y=t;} 24 for(t=deep[x]-deep[y],i=0;t>0;t>>=1,i++) 25 if(t&1) x=anc[x][i]; 26 if(x==y) return x; 27 for(i=log2n;i>=0;i--) 28 if(anc[x][i]!=anc[y][i]) 29 { 30 x=anc[x][i]; 31 y=anc[y][i]; 32 } 33 return anc[x][0]; 34 } 35 int main() 36 { 37 int i,x,y,a,b; 38 scanf("%d%d%d",&n,&m,&s); 39 while((1<<(log2n+1))<=n) log2n++; 40 for(i=1;i<n;i++) 41 { 42 scanf("%d%d",&x,&y); 43 e[++ne].to=y; 44 e[ne].next=f1[x]; 45 f1[x]=ne; 46 e[++ne].to=x; 47 e[ne].next=f1[y]; 48 f1[y]=ne; 49 } 50 dfs(s,0); 51 while(m--) 52 { 53 scanf("%d%d",&a,&b); 54 printf("%d ",lca(a,b)); 55 } 56 return 0; 57 }
How far away ？ HDU - 2586（求树上两点距离）
方法就是求出dis[i]表示i到根节点的距离，那么两点a,b距离就是$dis[a]+dis[b]-2*dis[lca(a,b)]$
错误笔记：
1.20行写成anc[x][i]=anc[fa][i-1];
2.遗漏18行
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 struct Edge 8 { 9 LL to,d,nxt; 10 }e[80100]; 11 LL T,n,m,ne; 12 LL f1[40100],deep[40100],anc[40100][17],log2n; 13 LL dis[40100]; 14 void dfs(LL x,LL fa) 15 { 16 LL i,k; 17 anc[x][0]=fa; 18 deep[x]=deep[fa]+1; 19 for(i=1;i<=log2n;i++) 20 anc[x][i]=anc[anc[x][i-1]][i-1]; 21 for(k=f1[x];k!=0;k=e[k].nxt) 22 if(e[k].to!=fa) 23 { 24 dis[e[k].to]=dis[x]+e[k].d; 25 dfs(e[k].to,x); 26 } 27 } 28 LL lca(LL x,LL y) 29 { 30 LL t,i; 31 if(deep[x]<deep[y]) swap(x,y); 32 for(t=deep[x]-deep[y],i=0;t>0;t>>=1,i++) 33 if(t&1) x=anc[x][i]; 34 if(x==y) return x; 35 for(i=log2n;i>=0;i--) 36 if(anc[x][i]!=anc[y][i]) 37 { 38 x=anc[x][i]; 39 y=anc[y][i]; 40 } 41 return anc[x][0]; 42 } 43 int main() 44 { 45 LL i,a,b,w,t; 46 scanf("%lld",&T); 47 while(T--) 48 { 49 ne=0; 50 memset(f1,0,sizeof(f1)); 51 scanf("%lld%lld",&n,&m); 52 log2n=log2(n); 53 for(i=1;i<n;i++) 54 { 55 scanf("%lld%lld%lld",&a,&b,&w); 56 e[++ne].to=b; 57 e[ne].nxt=f1[a]; 58 e[ne].d=w; 59 f1[a]=ne; 60 e[++ne].to=a; 61 e[ne].nxt=f1[b]; 62 e[ne].d=w; 63 f1[b]=ne; 64 } 65 dfs(1,0); 66 for(i=1;i<=m;i++) 67 { 68 scanf("%lld%lld",&a,&b); 69 t=lca(a,b); 70 printf("%lld ",dis[a]-dis[t]+dis[b]-dis[t]); 71 } 72 } 73 return 0; 74 }
洛谷 P1967 货车运输（求图中给定两点间的所有路径中，最短边最长的一条路径的最短边）
首先，可以直接取原图的最大生成树，只在这之上查询答案。
原因是，在kruskal生成最大生成树的过程中，是按边权从大到小取边。在判断某条边取不取时，只有两点已经连通，才会不取边，否则一定会取。而如果在判断是否取一条(a,b,w)的边时，a和b已经连通，那么使得a和b连通的路径上任意一条边的权值都一定大于等于w（由于它们都在当前边之前取），也就是使得a和b连通的路径上的最小边权大于等于w。那么对于某两点间路径，如果需要过a到b的路径，那么选择(a,b,w)的路径一定不会比选择使得a和b连通的原来路径更好。
那么，这道题和前面一道就类似了，不过由于最大最小值不满足区间加和，不能简单的像那一道一样用前缀和。正确的方法类似倍增lca求2^i级祖先的过程。
设minn[i][j]表示点i到其2^j级祖先的路径上的最小边权。那么$minn[i][j]=min(minn[i][j-1],minn[anc[i][j-1]][j-1])$。当然，minn[i][0]就是其到父亲的边的边权。这个数组在倍增lca的dfs中可以预处理出来。
在查询的时候，就用倍增lca的查询，但是对于节点向上跳的操作，进行之前应当先把将要跳过的这段路径的最小边权更新到已知的最小边权之上。
错误记录（本地）：
1.47、48行打反
2.35行写成anc[e[k].to]=fa
3.缺少87行
4.缺少66行
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 struct E1 7 { 8 int a,b,w; 9 friend bool operator<(const E1& a,const E1& b) 10 { 11 return a.w>b.w; 12 } 13 }e1[50100]; 14 struct Edge 15 { 16 int to,d,nxt; 17 }e[20100]; 18 int fa[10100],q,n,m,ne,f1[10100],anc[10100][15],log2n,minn[10100][15],deep[10100]; 19 int find(int x) 20 { 21 return fa[x]==x?x:fa[x]=find(fa[x]); 22 } 23 void dfs(int x,int fa) 24 { 25 int i,k; 26 for(i=1;i<=log2n;i++) 27 { 28 anc[x][i]=anc[anc[x][i-1]][i-1]; 29 minn[x][i]=min(minn[x][i-1],minn[anc[x][i-1]][i-1]); 30 } 31 for(k=f1[x];k!=0;k=e[k].nxt) 32 if(e[k].to!=fa) 33 { 34 deep[e[k].to]=deep[x]+1; 35 anc[e[k].to][0]=x; 36 minn[e[k].to][0]=e[k].d; 37 dfs(e[k].to,x); 38 } 39 } 40 int get(int x,int y) 41 { 42 int t,ans=0x3f3f3f3f,i; 43 if(deep[x]<deep[y]) swap(x,y); 44 for(t=deep[x]-deep[y],i=0;t>0;t>>=1,i++) 45 if(t&1) 46 { 47 ans=min(ans,minn[x][i]); 48 x=anc[x][i]; 49 } 50 if(x==y) return ans; 51 for(i=log2n;i>=0;i--) 52 if(anc[x][i]!=anc[y][i]) 53 { 54 ans=min(ans,minn[x][i]); 55 ans=min(ans,minn[y][i]); 56 x=anc[x][i]; 57 y=anc[y][i]; 58 } 59 return min(ans,min(minn[x][0],minn[y][0])); 60 } 61 int main() 62 { 63 int i,t1,t2,a,b; 64 scanf("%d%d",&n,&m); 65 log2n=log2(n); 66 memset(minn,0x3f,sizeof(minn)); 67 for(i=1;i<=m;i++) 68 scanf("%d%d%d",&e1[i].a,&e1[i].b,&e1[i].w); 69 sort(e1+1,e1+m+1); 70 for(i=1;i<=n;i++) 71 fa[i]=i; 72 for(i=1;i<=m;i++) 73 { 74 t1=find(e1[i].a); 75 t2=find(e1[i].b); 76 if(t1==t2) continue; 77 e[++ne].to=e1[i].b; 78 e[ne].nxt=f1[e1[i].a]; 79 e[ne].d=e1[i].w; 80 f1[e1[i].a]=ne; 81 e[++ne].to=e1[i].a; 82 e[ne].nxt=f1[e1[i].b]; 83 e[ne].d=e1[i].w; 84 f1[e1[i].b]=ne; 85 fa[t1]=t2; 86 } 87 dfs(1,0); 88 scanf("%d",&q); 89 while(q--) 90 { 91 scanf("%d%d",&a,&b); 92 if(a>n||b>n||find(a)!=find(b)) 93 { 94 printf("-1 "); 95 continue; 96 } 97 printf("%d ",get(a,b)); 98 } 99 return 0; 100 }
洛谷p3379模板最近公共祖先（lca）
洛谷P3379【模板】最近公共祖先（LCA）题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序... 查看详情
lca（洛谷p3379最近公共祖先（lca））
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先.输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之... 查看详情
洛谷——p3379模板最近公共祖先（lca）
https://www.luogu.org/problem/show?pid=3379#sub题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的... 查看详情
洛谷p3379模板最近公共祖先（lca）如题
P3379【模板】最近公共祖先（LCA）时空限制1s/512MB题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数... 查看详情
洛谷p3379模板最近公共祖先（lca）题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=3379题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：... 查看详情
[洛谷p3379]模板最近公共祖先（lca）
题目大意：给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。题解：有多种做法，我这边用了倍增和树链剖分（都是在线而且好像都不是很快。。。） 倍增：（写于2017-9-13）bfs函数：处理每个节点的深度（其实... 查看详情
洛谷p3379模板最近公共祖先（lca）(代码片段)
P3379【模板】最近公共祖先（LCA）题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序... 查看详情
洛谷p3379模板最近公共祖先（lca）
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整... 查看详情
洛谷p3379模板最近公共祖先（lca）
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x... 查看详情
rmq洛谷p3379rmq求lca
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整... 查看详情
洛谷p3379模板最近公共祖先（lca）（树链剖分）
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整... 查看详情
[hdu]p2586howfaraway?[lca]
[HDU]P2586Howfaraway？TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):18675 AcceptedSubmission(s):7274ProblemDes 查看详情
树链剖分洛谷p3379树链剖分求lca
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整... 查看详情
hdu2586lca
LCA模板题。DFS记录好，到根结点的距离。#include<bits/stdc++.h>usingnamespacestd;constintmaxn=40000+5;constintlogmaxn=20;structEdge{intto,w;};std::vector<Edge>G[maxn];intf[maxn],dis[maxn],deep[maxn],p[maxn] 查看详情
hdu2586howfaraway？倍增lca
hdu2586Howfaraway？倍增LCA题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2586思路：针对询问次数多的时候，采取倍增求取LCA，同时跟新距离数组因为(2^{16}>40000)所以所以表示祖先的数组dp[][]第二维取到16即可就这道题来说，与比较tarjan... 查看详情
hdu-2586howfaraway？（暴力|lca）(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586题目：ProblemDescriptionTherearenhousesinthevillageandsomebidirectionalroadsconnectingthem.Everydaypeolealwaysliketoasklikethis"HowfarisitifIwanttogofro 查看详情
hdu2586（lca模板）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2586还是要多练习，不够熟练。。可以一看：http://blog.csdn.net/nameofcsdn/article/details/522305481#include<cstdio>2#include<cstring>3#include<cmath>4#incl 查看详情
hdu2586---howfaraway？（lca算法）(代码片段)
ProblemDescriptionTherearenhousesinthevillageandsomebidirectionalroadsconnectingthem.Everydaypeolealwaysliketoasklikethis"HowfarisitifIwanttogofromhouseAtohouseB"?Usuallyithardtoanswer.Butluckilyintth 查看详情