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.