最近公共祖先LCAC++版

1、LCA最近公共祖先首先是最近公共祖先的概念(什么是最近公共祖先？):深度最大的公共的祖先节在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上换句话说，就是两个点在这棵树上距离最近的公共祖先节点所以LCA主要是用来处理当两个点仅有 唯一一条确定的最短路径时的路径。有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点举个例子吧，如下图所示 4和5的最近公共祖先是2 , 5和3的最近公共祖先是1 , 2和1的最近公共祖先 是1。这就是最近公共祖先的基本

2、概念了，那么我们该如何去求这个最近 公共祖先呢?通常初学者都会想到最简单粗暴的一个办法：对于每个询问，遍历所有的点，时间复杂度为O(n*q)，很明显，n和q 一般不会很小。常用的求LCA的算法有：Tarjan/DFS+ST/ 倍增之间。后两个算法都是在线算法，也很相似，时间复杂度在O(logn)O(nlogn)O(n+q)。什么是Tarjan(离线(塔尔杨)算法呢？顾名思义，就是在一次遍历中把所有询问一次性解决，所以其时间复杂度是Tarjan算法的优点在于相对稳定，时间复杂度也比较居中，也很容易理解。下面详细介绍一下Tarjan算法的基本思路:1 .任选一个点为根节点，从根节点开始。2 .遍历

3、该点u所有子节点v ,并标记这些子节点 v已被访问过。3 .若是v还有子节点，返回2 ,否则下一步。4 .合并v到u上。5 .寻找与当前点u有询问关系的点v6 .若是v已经被访问过了，则可以确认 u和v的最近公共祖先为v被合并到的父亲节点a遍历的话需要用到dfs来遍历(我相信来看的人都懂吧.)，至于合并，最优化的方式就是利用并查集来合并两个节点。下面上伪代码:1 Tarjan(u) /marge 和find为并查集合并函数和查找函数foreach(u,v)/访问所有u子节点vTarjan(v);/继续往下遍历marge(u,v);/合并v至！ J u上标记v被访问过；foreach(u,e)

4、/访问所有和u有询问关系的e1011如果e被访问过；12u,e的最近公共祖先为find(e);1314个人感觉这样还是有很多人不太理解，所以我打算模拟一遍给大家看。建议拿着纸和笔跟着我的描述一起模拟！ ！假设我们有一组数据 9个节点8条边联通情况如下：1-2 , 1-3 , 2-4 , 2-5 , 3-6 , 5-7 , 5-8 , 7-9即下图所示的树设我们要查找最近公共祖先的点为9-8 , 4-6 , 7-5 , 5-3 ;0；设f数组为并查集的父亲节点数组，初始化 fi=i , vis数组为是否访问过的数组，初始为f1=1; vis1=flase;f2-2; vis2=flase; f3

5、1=3； vis3=flase; f4=4; vis4=flase; f5=S; vis55=flase; f6=6; vis6=flase; f7 = 7; vis7=flase; f8=8; vis8=flase; f9=9； vis9=flase;下面开始模拟过程:取1为根节点，往下搜索发现有两个儿子2和3 ;先寸t 2 ,发现2有两个儿子4和5,先搜索4 ,发现4没有子节点，则寻找与其有关系的点;发现6与4有关系，但是vis6=0,即6还没被搜过，所以 不操作；发现没有和4有询问关系的点了，返回此前一次搜索，更新vis4=1vis4=flase;I vis6=flase;I vis4=

6、true;I f4=2;表示4已经被搜完，更新f4=2,继续搜5 ,发现5有两个儿子7和8;先搜7,发现7有一个子节点9,搜索9,发现没有子节点，寻找与其有关系的点；发现8和9有关系，但是vis8=0，即8没被搜到过，所以不操作；发现没有和9有询问关系的点了，返回此前一次搜索，更新vis9=1;表示9已经被搜完，更新f9=7,发现7没有没被搜过的子节点了，寻找与其有关系的点;发现5和7有关系，但是vis5=0,所以不操作；发现没有和7有关系的点了，返回此前一次搜索，更新vis7=1表示7已经被搜完，更新f7=5,继续搜8 ,发现8没有子节点，则寻找与其有关系的点;发现9与8有关系，此时vis9

7、=1,则他们的最近公共祖先 为find(9)=5;(find(9) 的顺序为 f9=7-f7=5-f5=5 return 5;)发现没有与8有关系的点了，返回此前一次搜索，更新vis8=1;(find(7) 的顺序为 f7=5-f5=5 return 5;)又发现5和3有关系，但是vis3=0,所以不操作,此时5的子节点全部搜完了;返回此前一次搜索，更新vis5=1,表示5已经被搜完，更新f5=2发现2没有未被搜完的子节点，寻找与其有关系的点;又发现没有和2有关系的点，则此前一次搜索,更新 vis2=1表示2已经被搜完，更新f2=1,继续搜3,发现3有一个子节点6;搜索6 ,发现6没有子节点，

8、则寻找与 6有关系的点，发现4和6有关系;此时vis4=1,所以它们的最近公共祖先为find(4)=1(find(4)的顺序为 f4=2-f2=2-f1=1 return 1;)发现没有与6有关系的点了，返回此前一次搜索，更新vis6=1,表示6已经被搜完了;(find(5)的顺序为 f5=2-f2=1-f1=1 return 1;)发现没有和3有关系的点了，返回此前一次搜索，更新vis3=1红色表示僵索急径曲线表示合并路径vis31=flase;I vrs5-tnie;I find(5)=1;=5 and 3 =1I ui43抖LI更新13=1,发现1没有被搜过的子节点也没有有关系的点，此时

9、可以退出整个dfs 了。经过这次dfs我们得出了所有的答案，有没有觉得很神奇呢？是否对 Tarjan算法有更深层次的理解了呢?如果有什么不懂可以在下面 留言提问or发送问题到1136404654。推荐几道LCA的题目CODEVS 2370小机房的树传送门CODEVS 1036商务旅行传送门METO CODE 223 拉力赛 传送门HDU 2586 How far way? 传送门ZOJ 3195 Design the city 传送门CODEVS103酶务旅行题目描述 Description某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。假设有N个城镇，

10、首都编号为1,商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇,并且公路网络不会存在环。你的任务是帮助该商人计算一下他的最短旅行时间。输入描述 Input Description输入文件中的第一行有一个整数N, 1=n=30 000,为城镇的数目。下面N-1行，每行由两个整数a和b (1=a,b=n; ab)组成，表示城镇a和城镇b有公路连接。在第 N+1行为一个整数 M,下面的M行，每行有该商人需要顺次经过的各城镇编号。输出描述 Output Description在输出文件中输出该商人

11、旅行的最短时间。样例输入Sample Input51 21 53 54 541325样例输出Sample Output7#includestruct nodeint to,next,ljj;e60001,qe60001;int n,m,fa30001,head30001,qhead30001,ans=0,cnt=0,pjy30001;bool b30001,bb30001;int ask(int x)if(x=fax) return fax;return fax=ask(fax);void addedge(int x,int y)e+cnt.to=y;ecnt.next=headx;headx

12、=cnt;void addedge2(int x,int y,int z)qe+cnt.to=y;qecnt.ljj=z;qecnt.next=qheadx;qheadx=cnt;void tarjan(int u)bu=1; fau=u;for (int i=headu;i;i=ei.next)if (!bei.to)pjyei.to=pjyu+1;tarjan(ei.to);faei.to=u;)for (int i=qheadu;i;i=qei.next) if (bqei.to&!bbqei.ljj)ans+=pjyqei.to+pjyu卜2*pjyask(qei.to); bbqei

13、.ljj=1;)int main()scanf(%d,&n);int x,y;for (int i=1;in;i+)scanf(%d%d,&x,&y);addedge(x,y);addedge(y,x);)cnt=0;int T;scanf(%d,&T);scanf(%d,&x);for (int i=2;i=T;i+)scanf(%d,&y);addedge2(x,y,i-1);addedge2(y,x,i-1);x=y;)pjy1=0;tarjan(1);printf(%d,ans);return 0;)/*离线tarjan+并查集.关于邻接链表边的标号的初始化问题.若第一条边标号为 0则

14、需初始化head1n=-1, 因为搜索的时候必定会搜到headu=0然后需判i!=-1若第一条边编号为1则只需判i!=0 无需初始化.切记.*/#include#include#include#define MAXN 50001using namespace std;int n,m,headMAXN,ans,faMAXN,lcMAXN,tot,cut,deepMAXN,head2MAXN;bool bMAXN,b2MAXN;struct dataint v;int next;eMAXN1,sMAXN1;void add_edge(int u,int v)etot.v=v;etot.next=h

15、eadu;headu=tot+;void add(int u,int v)scut.v=v;scut.next=head2u;head2u=cut+;void dfs(int x,int father)deepx=deepfather+1;bx=true;for(int i=headx;i!=-1;i=ei.next)if(!bei.v) dfs(ei.v,x);int find(int x)if(x=fax) return fax;return fax=find(fax);void lcatarjan(int u)fau=u;bu=true;for(int i=headu;i!=-1;i=e

16、i.next)if(bei.v) continue;lcatarjan(ei.v);fafind(ei.v)=find(u);lcfind(u)=u;)for(int i=head2u;i;i=si.next)(if(b2si.v)(ans+=deepu+deepsi.v卜2*deeplcfind(si.v);)b2u=true;)int main()(memset(head,-1,sizeof(head);memset(head2,-1,sizeof(head2);int x,y;scanf(%d,&n);for(int i=1;in;i+)(scanf(%d%d,&x,&y);add_ed

17、ge(x,y);add_edge(y,x);)int u=1,v;scanf(%d,&m);for(int i=1;i=m;i+)(scanf(%d,&v);add(u,v);add(v,u);u=v;)dfs(1,0);memset(b,0,sizeof(b);lcatarjan(1);printf(%d,ans);return 0;)/*第一种，倍增(O(nlogn)O(logn),在线)：倍增的思想用在树上，即可以求出lca。就是他的父亲我们维护二维数组，fij,表示i号点白第2寸号祖先，显然2A0=1也就是fi0 我们需要用dfs维护一个深度数组(求lca需要用)还需要倍增求出所有的f

18、ij,学过st的都应该知道，在这里fij=f fij-1 j然后是我们的求lca 了，很简单，首先要将这两个点u和v调到同一深度，这样以后操作都是同深度的。怎么调深度呢？很简单，将他们的深度相减，我们设为dep,那么这个dep的就对应了深一点的那个点需要上升的高度，恩，应该马上能想到，直接用二进制表示深度然后一直爬上去就行了，这就是倍增的思想,log级别 同一深度时，我们要同时上升啦我们继续用倍增思想，依次上升 2”的高度。什么时候上升呢？当然是 fuk!=fvk 的时候，因为这说明他们的祖先还不同，他们位于2棵子树，所以要上升。并且顺序要从大到小！否则求不到最小的祖先，很容易理解的。*/不存

19、在#include#include#include#define MAXN 30001#define D 20using namespace std;struct dataint v;int next;int z;eMAXN*2;int tot,deepMAXN,faMAXND+5,n,m,headMAXN;void add_edge(int u,int v)tot+;etot.v=v;etot.next=headu;headu=tot;void dfs(int now,int father,int d)/建树.fanow0=father;deepnow=d;for(int i=headnow

20、;i;i=ei.next)if(father!=ei.v)(dfs(ei.v,now,d+1);)void get_father()处理出每个节点的2”(for(int j=1；j=D；j+)for(int i=1;i=n;i+)faij=fafaij-1j-1;)int get_same(int a,int b)/二进制使 u,v 在同一深度.(for(int i=0;i=D;i+)if(b&(1i) a=faai;return a;)int lca(int u,int v)(if(deepu=0;i-)/ if(faui!=favi) (u=faui;v=favi;)return fau0

21、;/)int main()(scanf(%d,&n);int x,y;for(int i=1;i=n-1;i+)/(scanf(%d%d,&x,&y);add_edge(x,y);add_edge(y,x);)是v父亲时.向上搜到lea的儿子.此时u为lea的子节点. 一般是n-1条边.dfs(1,1,0);get_father();int u,v;tot=0;scanf(%d%d,&m,&u);for(int i=1;im;i+) (scanf(%d,&v);int LCA=lca(u,v);tot+=(deepu+deepM-2*deepLCA);数学方法.u=v;printf(%d,to

22、t);return 0;CODEVS 2370小机房的树题目描述 Description小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1,有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费c的能量(从父亲节点爬到此节点也相同)，他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉 他们最少需要花费多少精力输入描述 Input Description第一行一个n,接下来n-1行每一行有三个整数u,v, c 。表示节点u爬

23、到节点v需要花费c的精力。第n+1行有一个整数 m表示有m次询问。接下来 m行每一行有两个整数u , v表示两只虫子所在的节点输出描述 Output Description一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。样例输入Sample Input31 0 12 0 131 02 01 2样例输出Sample Output112数据范围及提示 Data Size & Hint1=n=50000, 1=m=75000, 0=c=1000#include#include#define M 1000001using namespace std;int fM31;int disM;s

24、truct node int to,next;int val;)；node eM;int tot,headM;int n,m;int deepM;inline int read(int&x) x=0;char c=getchar();while(c9|c=0&c=9) x=10*x+c-48,c=getchar();)inline void dfs(int now,int from,int dep,int v) deepnow=dep;fnow0=from;disnow=v+disfrom;for(int i=headnow;i;i=ei.next) int u=ei.to;if(u!=fro

25、m) dfs(u,now,dep+1,ei.val);)/*inline void dfs(int u,int dep) /两种 dfs 姿势都可以deepu=dep;for(int i=headu;i;i=ei.next) int v=ei.to;if(!deepv&v) fv0=u;disv=disu+ei.val;dfs(v,dep+1);)*/inline void add(int x,int y,int z) e+tot.to=y;etot.val=z;etot.next=headx;headx=tot;inline int LCA(int a,int b) int ans=0;if

26、(deepadeepb) swap(a,b);int t=deepa-deepb;for(int i=0;i=30;i+)if(1=0;i-)if(fai!=fbi)a=fai,b=fbi;return fa0;)int main() read(n);for(int i=1;in;i+) int x,y,z;read(x);read(y);read(z);x+;y+;add(x,y,z);add(y,x,z);)dfs(1,1,0,0);for(int j=1;j=30;j+)for(int i=1;i=n;i+)fij=ffij-1j-1;read(m);for(int i=1;i=m;i+

27、) int x,y;read(x);read(y);x+;y+;int lca=LCA(x,y);if(lca=x) printf(%dn,disy-disx);else printf(%dn,disx+disy-2*dislca);)return 0;)POJ1986题意：LCA模板题，输入n和m,表示n个点m条边，下面m行是边的信息，两端点和权，后面的那个 字母无视掉，没用的。接着下面k个询问两个点之间的最短距离，输出即可 .Sample Input7 61 6 13 E6 3 9 E3 5 7 S4 1 3 N2 4 20 W4 7 2 S31 62 43 6Sample Output1

28、3 336HintFarms 2 and 6 are 20+3+13=36 apart.#include #include #include #include #include #include #include using namespace std;int n,m,q;int up233333,de233333,dp23333323,fa233333;int pn233333,pg233333,pv233333,st233333;int tot=0;void init()memset(up,0,sizeof(up);memset(de,0,sizeof(de);memset(dp,0,si

29、zeof(dp);memset(pn,0,sizeof(pn);memset(pg,0,sizeof(pg);memset(pv,0,sizeof(pv);memset(fa,0,sizeof(fa);return ;void ins(int x,int y,int w)pv+tot=y;pgtot=w;pntot=stx;stx=tot;return;void dfs(int x)dpx0=fax;for(int i=1;i20;i+) dpxi=dpdpxi-1i-1; for (int i=stx;i;i=pni)(int cur=pvi;if (cur=fax) continue;de

30、cur=dex+1;upcur=upx+pgi;facur=x; dfs(cur);)return;)int lca(int x,int y)(if (dex=0;i-)if (dedpxi=dey) x=dpxi;)if (x=y) return x;for (int i=19;i=0;i-)if (dpxi!=dpyi)x=dpxi;y=dpyi;)return dpx0;) int main() while(scanf(%d%d,&n,&m)init();int a,b,c;for (int i=1;i=m;i+)(char s10;scanf(%d%d%d%s,&a,&b,&c,s);

31、ins(a,b,c); ins(b,a,c);fa1=1;de1=up1=0;dfs(1);scanf(%d,&q);while(q-)(scanf(%d%d,&a,&b);printf(%dn,upa+upb-2*uplca(a,b);求树上距离。return 0;NOIP2016D1T2天天爱跑步题目描述小c同学认为跑步非常有趣，于是决定制作一款叫做天天爱跑步的游戏。天天爱跑步是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。这个游戏的地图可以看作一棵包含N个结点和N-1条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有 m个玩

32、家，第i个玩家的起点为 Si ,终点为Ti 。每天打卡任务开始时，所有玩家在第0秒 同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点的观察员会选择在第 Wj秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点 J 。小C想知道每个观察员会观察到多少人？注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。即对于把结点J作为终点的玩家：若他在第W

33、j秒重到达终点，则在结点J的观察员不能观 察到该玩家；若他正女?在第 Wj秒到达终点，则在结点的观察员可以观察到这个玩家。Input第一行有两个整数 N和M。其中N代表树的结点数量，同时也是观察员的数量，M代表玩家的数量。接下来n-1行每行两个整数 U和V ,表示结点U到结点V有一条边。接下来一行N个整数，其中第个整数为 Wj ,表示结点出现观察员的时间。接下来M行，每行两个整数 Si和Ti,表示一个玩家的起点和终点。 对于所有的数据，保证。1=Si,Ti=N,0=Wj=NOutput输出1行N个整数，第个整数表示结点的观察员可以观察到多少人。Sample Input 6 32 3 1 21

34、44 54 60 2 5 1 2 3 1 51 3 2 6 Sample Output 2 0 0 1 1 1 Sample Input 5 31 2 2 32 4 1 50 1 0 3 03 1 1 45 5Sample Output 1 2 1 0 1HINT对于1号点，Wi=0,故只有起点为1号点的玩家才会被观察到，所以玩家 1和玩家2被观察到，共有2人 被观察到。对于2号点，没有玩家在第 2秒时在此结点，共 0人被观察到。对于3号点，没有玩家在第 5秒时在此结点，共 0人被观察到。对于4号点，玩家1被观察到，共1人被观察到。对于5号点，玩家1被观察到，共1人被观察到。对于6号点，玩家3

35、被观察到，共1人被观察到。#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 300011;const int MAXM = 600011;intn,m,ecnt,firstMAXN,nextMAXM,toMAXM,fMAXN20,deepMAXN,ansMAXN,valMAXN,tongMA XN,MAXD,wMAX

36、N,num1000011;int headMAXN,ttMAXM,nnMAXM,fatherMAXN,visMAXN;vectorljhMAXN,ljh2MAXN,ljh3MAXN;struct node int s,t,lca,len;aMAXN; inline int getint()int w=0,q=0; char c=getchar(); while(c9) & c!=-) c=getchar();if(c=-)q=1,c=getchar(); while (c=0&c=9)w=w*10+c-0,c=getchar(); returnq?-w:w; inline void link(

37、int x,int y) next+ecnt=firstx; firstx=ecnt; toecnt=y; inline void LINK(int x,int y) nn+ecnt=headx; headx=ecnt; ttecnt=y; inline int find(int x) if(fatherx!=x) fatherx=find(fatherx); return fatherx; inline void init(int x,int fa)fatherx=x; visx=1;for(int i=headx;i;i=nni) int v=tti;if(x=av.s&visav.t)

38、av.lca=find(av.t);if(x=av.t&visav.s) av.lca=find(av.s);for(int i=firstx;i;i=nexti) int v=toi; if(v=fa) continue;deepv=deepx+1; init(v,x); fatherv=x;fv0=x;inline int lca(int x,int y)if(deepxdeepy) swap(x,y); int t=0; while(1t)=0;i-) if(deepx-(1=deepy) x=fxi; if(x=y) return y;for(int i=t;i=0;i-) if(fx

39、i!=fyi) x=fxi,y=fyi; return fx0; inline void dfs(int x,int fa)int now=wx+deepx,cun; if(now=MAXD) cun=tongnow;for(int i=firstx;i;i=nexti) int v=toi; if(v=fa) continue; dfs(v,x);)tongdeepx+=valx; if(now=MAXD) ansx=tongnow-cun;for(int i=0,ss=ljhx.size();iss;i+) tongdeepljhxi-;)inline void DFS(int x,int

40、 fa)int now=deepx-wx,cun; now+=300000; cun=numnow;for(int i=firstx;i;i=nexti) int v=toi; if(v=fa) continue;DFS(v,x);)for(int i=0,ss=ljh2x.size();iss;i+) num300000+ljh2xi+;ansx+=numnow卜cun;for(int i=0,ss=ljh3x.size();iss;i+) num300000+ljh3xi-;)inline void work()n=getint(); m=getint(); int x,y; for(in

41、t i=1;in;i+) x=getint(); y=getint(); link(x,y);link(y,x); )for(int i=1;i=n;i+) wi=getint(); ecnt=0;for(int i=1;i=m;i+) ai.s=getint(),ai.t=getint(),valai.s+;LINK(ai.s,i);LINK(ai.t,i);deep1=1; init(1,0); for(int i=1;i=n;i+) MAXD=max(MAXD,deepi);for(int j=1;j=19;j+) for(int i=1;i=n;i+) fij=ffij-1j-1;fo

42、r(int i=1;i=m;i+) ai.len=deepai.s+deepai.t-deepai.lca*2;ljhai.lca.push_back(ai.s);dfs(1,0);for(int i=1;i=m;i+) ljh2ai.t.push_back(deepai.t-ai.len);ljh3ai.lca.push_back(deepai.t-ai.len);DFS(1,0);for(int i=1;i=m;i+) if(deepai.s-deepai.lca=wai.lca) ansai.lca-;for(int i=1;i=n;i+) printf(%d,ansi); if(in) printf( ); int main()work();return 0;另一种解法：#include#include#include#define fo(i,a,b) for(int i=a;i=b;i-)#define N 301000using namespace std;intwN,lastN*10,nextN*10,toN*10,tot=0,n,m,dfnN,faN,sonN,topN,sizeN,gN+N+N,d e