hdu 2586 How far away ？倍增LCA

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2586

思路：

• 针对询问次数多的时候，采取倍增求取LCA，同时跟新距离数组
• 因为
• \(2^{16} > 40000\)
• 所以所以表示祖先的数组dp[][]第二维取到16即可
• 就这道题来说，与比较tarjan比较，稍快一点

代码：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

#include <math.h>

using namespace std;

const int maxn = 40005;

const int maxm = 80005;

struct node {

    int to,next,w;

}edges[maxm];

int head[maxn],cnt,dp[maxn][17],dep[maxn],dist[maxn];

inline void addedge(int u, int v, int w) {

    edges[cnt].to=v;

    edges[cnt].w=w;

    edges[cnt].next=head[u];

    head[u]=cnt++;

}

void dfs(int s, int x) {

    dp[s][0]=x;

    dep[s]=dep[x]+1;

    int t;

    for(int i=1;(1<<i)<=dep[s];++i)

        dp[s][i]=dp[dp[s][i-1]][i-1];

    for(int i=head[s];i!=-1;i=edges[i].next) {

        t=edges[i].to;

        if(t==x) continue;

        dist[t]=dist[s]+edges[i].w;

        dfs(t,s);

    }

}

inline int lca(int u, int v) {

    if(dep[v]>dep[u]) swap(u,v);

    for(int i=16;i>=0;--i) {

        if((1<<i)<=(dep[u]-dep[v])) {

            u=dp[u][i];

        }

    }

    if(u==v) return u;

    for(int i=16;i>=0;--i) {

        if((1<<i)<=dep[u]&&(dp[v][i]!=dp[u][i])) {

            u=dp[u][i];

            v=dp[v][i];

        }

    }

    return dp[u][0];

}

inline int slove(int u ,int v) {

    int z=lca(u,v);

    return dist[u]-2*dist[z]+dist[v];

}

inline void init() {

    cnt=0;

    memset(head,-1,sizeof(head));

}

int main() {

    int t,n,m,u,v,w;

    scanf("%d",&t);

    while(t--) {

        scanf("%d %d",&n,&m);

        init();

        for(int i=1;i<n;++i) {

            scanf("%d %d %d",&u,&v,&w);

            addedge(u,v,w);

            addedge(v,u,w);

        }

        dep[1]=0;//保持dfs的统一，实际dep[1]=1

        dist[1]=0;

        dfs(1,1);

        for(int i=1;i<=m;++i) {

            scanf("%d %d",&u,&v);

            printf("%d\n",slove(u,v));

        }

    }

    return 0;

}