hdu2586 lca倍增法

倍增法加了边的权值，bfs的时候顺便把每个点深度求出来即可

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define maxn 40005

#define DEG 20

struct Edge{

    int to,next,w;

}edge[maxn*];

int head[maxn],tot;

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

    edge[tot].to=v;

    edge[tot].next=head[u];

    edge[tot].w=w;

    head[u]=tot++;

}

int fa[maxn][DEG];

int deg[maxn],depth[maxn];

int flag[maxn];

void bfs(int root){

    queue<int> que;

    deg[root]=;depth[root]=;

    fa[root][]=root;

    que.push(root);

    while(!que.empty()){

        int tmp=que.front();que.pop();

        for(int i=;i<DEG;i++)

            fa[tmp][i]=fa[fa[tmp][i-]][i-];

        for(int i=head[tmp];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(v==fa[tmp][])continue;

            deg[v]=deg[tmp]+;

            depth[v]=depth[tmp]+edge[i].w;

            fa[v][]=tmp;

            que.push(v);

        }

    }

}

int lca(int u,int v){

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

    int hu=deg[u],hv=deg[v],tu=u,tv=v;

    for(int det=hv-hu,i=;det;det>>=,i++)

        if(det&) tv=fa[tv][i];

    if(tu==tv) return tu;

    for(int i=DEG-;i>=;i--){

        if(fa[tu][i]==fa[tv][i]) continue;

        tu=fa[tu][i];tv=fa[tv][i];

    }

    return fa[tu][];

}

void init(){

    tot=;

    memset(flag,,sizeof flag);

    memset(head,-,sizeof head);

    memset(deg,,sizeof deg);

    memset(depth,,sizeof depth);

}

int main(){

    int T,n,q,u,v,w;

    cin >> T;

    while(T--){

        init();

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

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

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

            addedge(u,v,w);

            addedge(v,u,w);

            flag[v]=;

        }

        int root;

        for(int i=;i<=n;i++) if(!flag[i]){root=i;break;}

        bfs(root);

        while(q--){

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

            int tmp=lca(u,v);

            printf("%d\n",depth[u]+depth[v]-*depth[tmp]);

        }

    }

    return ;

}