HDU-2586 How far away（LCA）模闆

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

dis[a]為根節點到a的距離那麼2個節點的最短距離就是dis[a]-dis[b]-dis[lca(a,b)]*2

參考鄒老闆子，存一下。

倍增法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=40005;
struct node
{
    int ch,dis;
};
vector<node> G[MX];
int rdis[MX];
int fa[22][MX],dep[MX];

void dfs(int u,int f,int dis)
{
    fa[0][u]=f;
    rdis[u]=dis;
    dep[u]=dep[f]+1;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].ch;
        if(v==f)continue;
        dfs(v,u,dis+G[u][i].dis);
    }
}
void init(int n)
{
    memset(fa,0,sizeof(fa));
    dep[0]=0;
    dfs(1,0,0);
    for(int k=0;k+1<20;k++){
        for(int v=1;v<=n+n;v++)
        {
            if(!fa[k][v]){
                fa[k+1][v]=0;
            }else{
                fa[k+1][v]=fa[k][fa[k][v]];
            }
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    for(int k=0;k<20;k++)
    {
        if((dep[v]-dep[u])>>k&1){
            v=fa[k][v];
        }

    }
    if(u==v)return u;
    for(int k=20-1;k>=0;k--){
        if(fa[k][u]!=fa[k][v]){
            u=fa[k][u];
            v=fa[k][v];
        }
    }
    return fa[0][u];

}
int main()
{
   int t,n,m;
   scanf("%d",&t);
   while(t--){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) G[i].clear();
    int i,j,k;
    for(int c=0;c<n-1;c++){
        scanf("%d%d%d",&i,&j,&k);
        G[i].push_back({j,k});
        G[j].push_back({i,k});
    }
    init(n);
    int a,b;
    while(m--){
        scanf("%d%d",&a,&b);
        int ans=rdis[a]+rdis[b]-rdis[lca(a,b)]*2;
        printf("%d\n",ans);
    }

   }
	return 0;
}