#### 1.introduction↵
↵
As everyone knows, my friend [user:Billy2007,2020-04-16] 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.**_
↵
As everyone knows, my friend [user:Billy2007,2020-04-16] 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.**_
