HDU2586How far away? LCA

时间：2024-12-21 14:06:33

去博客园看该题解

题意

　　给出一棵树，以及每条边的权值，给出一些询问，每个询问是2个节点，求每个询问对应的2个节点的距离。

算法

　　LCA_Tarjan

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=+;

struct Edge{

    int cnt,x[N],y[N],z[N],nxt[N],fst[N];

    void set(){

        cnt=;

        memset(x,,sizeof x);

        memset(y,,sizeof y);

        memset(z,,sizeof z);

        memset(nxt,,sizeof nxt);

        memset(fst,,sizeof fst);

    }

    void add(int a,int b,int c){

        x[++cnt]=a;

        y[cnt]=b;

        z[cnt]=c;

        nxt[cnt]=fst[a];

        fst[a]=cnt;

    }

}e,q;

int T,n,m,from,to,dist,in[N],rt,dis[N],fa[N],ans[N];

bool vis[N];

void dfs(int rt){

    for (int i=e.fst[rt];i;i=e.nxt[i]){

        dis[e.y[i]]=dis[rt]+e.z[i];

        dfs(e.y[i]);

    }

}

int getf(int k){

    return fa[k]==k?k:fa[k]=getf(fa[k]);

}

void LCA(int rt){

    for (int i=e.fst[rt];i;i=e.nxt[i]){

        LCA(e.y[i]);

        fa[getf(e.y[i])]=rt;

    }

    vis[rt]=;

    for (int i=q.fst[rt];i;i=q.nxt[i])

        if (vis[q.y[i]]&&!ans[q.z[i]])

            ans[q.z[i]]=dis[q.y[i]]+dis[rt]-*dis[getf(q.y[i])];

}

int main(){

    scanf("%d",&T);

    while (T--){

        q.set(),e.set();

        memset(in,,sizeof in);

        memset(vis,,sizeof vis);

        memset(ans,,sizeof ans);

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

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

            scanf("%d%d%d",&from,&to,&dist),e.add(from,to,dist),in[to]++;

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

            scanf("%d%d",&from,&to),q.add(from,to,i),q.add(to,from,i);

        rt=;

        for (int i=;i<=n&&rt==;i++)

            if (in[i]==)

                rt=i;

        dis[rt]=;

        dfs(rt);

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

            fa[i]=i;

        LCA(rt);

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

            printf("%d\n",ans[i]);

    }

    return ;

}

相关文章