最近公共祖先问题

1.进行树上倍增公共祖先模板

2.利用公共祖先性质，求三个点相互的公共祖先，找到不同的两个公共祖先

3.利用公共祖先的性质求距离（注意：最终答案是深度更大的公共祖先，这样保证了所有点不会公用一条线路）

python版本

推销一下下面的个人发明建边函数def Lin(a,b,c)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

def Lin(a,b):
    if a not in link.keys():
        link[a] = {b}
    else:
        link[a].add(b)

def bfs(root):
    queue = [root]
    depth[0] = 0
    depth[root] = 1
    while queue:
        curNode = queue.pop(0)

        if curNode not in link.keys():
            continue
        for node in link[curNode]:
            if depth[node] > depth[curNode] + 1:
                depth[node] = depth[curNode] + 1
                fa[node][0] = curNode
                for k in range(1,24):
                    fa[node][k] = fa[fa[node][k - 1]][k - 1]
                queue.append(node)

def lca(a,b):
    if depth[a] < depth[b]:
        a,b = b,a
    for k in range(23,-1,-1):
        if depth[fa[a][k]] >= depth[b]:
            a = fa[a][k]

    if a == b:
        return a

    for k in range(23,-1,-1):
        if fa[a][k] != fa[b][k]:
            a = fa[a][k]
            b = fa[b][k]

    return fa[a][0]


n,m = map(int,input().split())
fa = [[0]*(24) for i in range(n + 1)]
depth = [float('inf')]*(n + 1)

link = {}
for i in range(n - 1):
    a,b = map(int,input().split())
    Lin(a,b)
    Lin(b,a)
bfs(1)

for i in range(m):
    a,b,c = map(int,input().split())
    x = lca(a,b)
    y = lca(b,c)
    z = lca(c,a)
    if x == y: #确保x和y不重复
        y = z
    if depth[x] < depth[y]: #x在下
        x,y = y,x
    print(x,depth[a] + depth[b] + depth[c] - depth[x] - 2*depth[y])