HDU 2586 LCA离线算法 tarjan算法

LCA tarjan算法模板题

 题意：给一个无根树，有q个询问，每个询问两个点，问两点的距离。

用tarjan离线算法算出每个询问的两点的最近公共祖先

ans[i]=dis[x[i]]+dis[y[i]]-2*dis[z[i]]; //  x[i],y[i]分别存储每次询问的两点，z[i]存储这两点的最近公共祖先

#include "stdio.h"
#include "string.h"

int tot,n,m;
int f[40010],x[40010],y[40010],z[40010],dis[40010],vis[40010],head[40010];

struct node
{
    int to,next,v;
}edge[80010];
void add_edge(int a,int b,int c)
{
    edge[tot].to=b;
    edge[tot].next=head[a];
    edge[tot].v=c;
    head[a]=tot++;
}

int fin(int x)
{
    if (f[x]!=x)
        return f[x]=fin(f[x]);
    return f[x];
}
void tarjan(int w)
{
    int i;
    vis[w]=1;
    f[w]=w;
    for (i=1;i<=m;i++)
    {
        if (vis[y[i]] && x[i]==w) z[i]=fin(y[i]);
        if (vis[x[i]] && y[i]==w) z[i]=fin(x[i]);

    }

    for (i=head[w];i!=-1;i=edge[i].next)
        if (vis[edge[i].to]==0)
        {
            dis[edge[i].to]=dis[w]+edge[i].v;
            tarjan(edge[i].to);
            f[edge[i].to]=w;
        }
}

int main()
{
    int t,a,b,c,i;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        tot=0;
        memset(head,-1,sizeof(head));
        for (i=1;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add_edge(a,b,c);
            add_edge(b,a,c);
        }

        memset(z,0,sizeof(z));
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for (i=1;i<=m;i++)
            scanf("%d%d",&x[i],&y[i]);

        dis[1]=0;
        memset(vis,0,sizeof(vis));
        tarjan(1);

        for (i=1;i<=m;i++)
            printf("%d\n",dis[x[i]]+dis[y[i]]-2*dis[z[i]]);

    }
    return 0;
}

HDU 2586 LCA离线算法 tarjan算法

原文：http://blog.csdn.net/u011932355/article/details/46963881