LCA树链剖分

Python 代码

n,m=map(int,input().split())
fa=[0 for _ in range(n+1)]
dep=[0 for _ in range(n+1)]
sz=[0 for _ in range(n+1)]
son=[0 for _ in range(n+1)]
top=[0 for _ in range(n+1)]
graph={i:[] for i in range(1,n+1)}
d_pa=[0 for _ in range(n+1)]#存储到父节点的距离
d_root=[0 for _ in range(n+1)]#存储到根节点的距离
for _ in range(n-1):
    u,v,k=map(int,input().split())
    graph[u].append((v,k))
    graph[v].append((u,k))

def dfs1(u,father): #初始化fa，dep，son
    fa[u]=father
    dep[u]=dep[father]+1
    sz[u]=1
    for v,k in graph[u]:
        if v!=father:
            d_pa[v]=k
            d_root[v]=d_root[u]+k
            dfs1(v,u)
            sz[u]+=sz[v]
            if sz[son[u]]<sz[v]:
                son[u]=v

def dfs2(u,t): #初始化top
    top[u]=t#记录链头
    if not son[u]: #无重儿子即返回
        return 
    dfs2(son[u],t) #搜重儿子
    for v,_ in graph[u]:
        if v==fa[u] or v==son[u]:
            continue
        dfs2(v,v) #搜轻儿子

def lca(u,v):
    while top[u]!=top[v]:
        if dep[top[u]]<dep[top[v]]:
            u,v=v,u
        u=fa[top[u]]
    return u if dep[u]<dep[v] else v
dfs1(1,0)
dfs2(1,1)
for _ in range(m):
    p,q=map(int,input().split())
    x=lca(p,q)
    print(d_root[p]+d_root[q]-2*d_root[x])