倍增法实现LCA（以HDU - 2586为例）

Bertha 。 2022-05-05 09:56 162阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：求树上任意两点之间的距离。   分析：LCA模板题，这是一棵无根树，把它转化为有根树，再用倍增LCA求出每个结点到根节点的距离，两点的距离：dist = dis\[u\] + dis\[v\] - 2 \* dis\[ LCA(u,v) \]，复杂度O（nlogn）。倍增法求LCA入门参考[https://blog.csdn.net/lw277232240/article/details/72870644][https_blog.csdn.net_lw277232240_article_details_72870644]，倍增法的本质是二进制拆分。 ##

## 代码： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e5+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int t,n,m,dis[N],fa[N][20],dep[N],vs[N];
    struct nd{
        int to,w;
    };
    vector<nd> g[N];
    
    void init() {
        for(int i=1;i<=n;i++) g[i].clear();
        mst(dis,0),mst(fa,0),mst(dep,0),mst(vs,0);
    }
    
    void dfs(int x) {///求出每个节点到根节点的距离、深度、父亲
        vs[x]=1;
        for(int i=0;i<g[x].size();i++) {
            nd tp=g[x][i];
            int v=tp.to,w=tp.w;
            if(vs[v]) continue;
            fa[v][0]=x;
            dis[v]=dis[x]+w;
            dep[v]=dep[x]+1;
            dfs(v);
        }
    }
    
    void bz() {///倍增预处理
        for(int j=1;j<20;j++)///fa[i][j]表示结点 i 的第2^j个祖先
            for(int i=1;i<=n;i++)
                fa[i][j]=fa[fa[i][j-1]][j-1];
    }
    
    int lca(int u,int v) {
        if(dep[u]<dep[v]) swap(u,v);///注意是交换u和v,不是交换dep[u]和dep[v]
        int d=dep[u]-dep[v];
        for(int i=0;i<20;i++)///先调整到同一深度
            if(d&(1<<i)) u=fa[u][i];
        if(u==v) return u;
        for(int i=19;i>=0;i--) {///注意是倒着for，二进制拆分，从大到小尝试
            if(fa[u][i]!=fa[v][i]) {
                u=fa[u][i];
                v=fa[v][i];
            }
        }
        return fa[u][0];
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
        while(~scanf("%d",&t)) {
            while(t--) {
                scanf("%d%d",&n,&m);
                init();
                for(int i=1;i<n;i++) {
                    int a,b,c;
                    scanf("%d%d%d",&a,&b,&c);
                    g[a].pb({b,c});
                    g[b].pb({a,c});
                }
                dep[1]=1,dis[1]=0;
                dfs(1);
                bz();
                for(int i=1;i<=m;i++) {
                    int u,v;
                    scanf("%d%d",&u,&v);
                    printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
                }
            }
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2586
[https_blog.csdn.net_lw277232240_article_details_72870644]: https://blog.csdn.net/lw277232240/article/details/72870644