BB

众所周知，LCA有N种方法。一种种慢慢学。。。

方法

1. 倍增求法

2. 待续...

Problem List

• POJ 1986

//POJ 1986 lca模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+5;
struct Edge{
    int to;
    int len;
};
vector<Edge> G[maxn];
int fa[maxn][21],dep[maxn],dist[maxn];
void dfs(int u)
{
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];//倍增DP
    for(int i=0;i<G[u].size();i++)
    {
        Edge &e=G[u][i];
        if(e.to==fa[u][0])continue;
        dep[e.to]=dep[u]+1;
        dist[e.to]=dist[u]+e.len;
        fa[e.to][0]=u;
        dfs(e.to);
    }
}
int lca(int x,int y)
{
    if(dep[x]>dep[y])swap(x,y);
    int  f=dep[y]-dep[x];
    for(int i=0;(1<<i)<=f;i++)//二进制的思想，总能到达同dep
        if((1<<i)&f)y=fa[y][i];
    if(y==x)return x;
    for(int i=20;i>=0;i--)//二进制思想，由大到小的减，总能到达1
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y,l;
    char c;
    for(int i=0;i<m;i++)
    {
        getchar();
        scanf("%d %d %d %c",&x,&y,&l,&c);
        G[x].push_back({y,l});
        G[y].push_back({x,l}); 
    }
    dfs(1);
    int k;
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]);
    }
}