Algorithm——LCA(Least Common Ancestors)

Правка en12, от Inversentropir-36, 2020-04-17 08:41:23

1.introduction

As everyone knows, my friend Billy2007 is not good at The algorithm of tree, So I and he write this blog.

LCA , that is, the recent Common ancestor, refers to the root tree, find out one or two nodes u and v recent Common ancestor.

2.how to ask LCA?

For example:

Given a tree with multiple branches, the public ancestor that is closest to the specified two points is requested.

Input: The first line contains three positive integers, $$$N,M,S$$$ which respectively represent the number of nodes in the tree, the number of inquiries, and the number of root nodes. Next, $$$n-1$$$ rows each contain two positive integers $$$x, y$$$ indicating that there is a directly connected edge between $$$x$$$ node and $$$y$$$ node (the data is guaranteed to form a tree). Next, $$$M$$$ rows each contain two positive integers $$$a$$$,$$$b$$$, which means that the nearest common ancestor of $$$a$$$ and $$$b$$$ is inquired.

Output: The output contains $$$M$$$ rows, each containing a positive integer, which in turn is the result of each query.

Guys,how to solve it?

2.1.Brute force(XD)

Let the two points search like merge-find set :

struct node{
     int bianh;
     int fa,chd[N/1000];
     node(){
         fa=0;
         bianh=0;
         memset(chd,0,sizeof(chd));
     }
 };
 int lca(int a,int b){
     if(a==b) return a;
     return lca(nd[a].fa,nd[b].fa);
 }

But there is some problem with this algorithm.

Obviously we don't know if $$$a$$$ is the father of $$$b$$$ or $$$b$$$ is the father of $$$a$$$.

This problem can be solved by depth-first search.

But, This algorithm will waste lots of Meomry.

And even if it were possible, the DFS time complexity is $$$O(n)$$$, every time the worst time complexity is $$$O(n)$$$, the total time complexity is $$$O(nm)$$$, will definitely TLE.

2.2.Multiplication algorithm

We can use the multiplication algorithm -- an algorithm that achieves $$$O(\log n)$$$ to ask the LCA by recording the first $$$2^i$$$ generation of $$$a$$$.

------------ Will update after 6 hours.

Теги lca, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en14 Английский Inversentropir-36 2020-04-17 08:42:35 0 (published)
en13 Английский Inversentropir-36 2020-04-17 08:41:41 2
en12 Английский Inversentropir-36 2020-04-17 08:41:23 34
en11 Английский Inversentropir-36 2020-04-17 08:40:35 12
en10 Английский Inversentropir-36 2020-04-17 08:39:51 471
en9 Английский Inversentropir-36 2020-04-16 16:55:36 131
en8 Английский Inversentropir-36 2020-04-16 13:28:52 325
en7 Английский Inversentropir-36 2020-04-16 13:25:09 177
en6 Английский Inversentropir-36 2020-04-16 13:20:49 55
en5 Английский Inversentropir-36 2020-04-16 13:16:42 4 Tiny change: 'integers, N,M,SN,M,SN,M,S which res' -> 'integers, $N,M,S$ which res'
en4 Английский Inversentropir-36 2020-04-16 13:14:05 659
en3 Английский Inversentropir-36 2020-04-16 13:10:09 2 Tiny change: 'oduction\nAs ever' -> 'oduction\n\nAs ever'
en2 Английский Inversentropir-36 2020-04-16 13:09:43 213
en1 Английский Inversentropir-36 2020-04-16 13:06:26 98 Initial revision (saved to drafts)