HDU - 2586 How far away ？（LCA模板题）

时间：2023-03-08 15:39:53
HDU - 2586 How far away ？（LCA模板题）
HDU - 2586
Time Limit: 1000MS   Memory Limit: 32768KB   64bit IO Format: %I64d & %I64u

Submit Status

Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases. 
  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n. 
  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

2

3 2

1 2 10

3 1 15

1 2

2 3

2 2

1 2 100

1 2

2 1

Sample Output

10

25

100

100

Source

题意是给你一棵带权树，以及任意两点，让你算出两点的距离。那么可以通过求两点的最近公共祖先（LCA），然后两点到根节点的距离的和减去两倍最近公共祖先到根节点的距离就是两点的距离了。求LCA可以用tarjan，是利用dfs的性质加上并查集找祖先的功能实现的。具体实现看代码

可以参考http://blog.csdn.net/l_bestcoder/article/details/52087126

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#define X first

#define Y second

using namespace std;

typedef pair<int,int> pii;

const int maxn=;

struct node

{

    int v,w,next;

} E[maxn*];

pii P[];

int cnt,head[maxn],Lca[maxn],n,m,dis[maxn],f[maxn];

bool vis[maxn];

void init()

{

    cnt=;

    memset(vis,,sizeof(vis));

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

}

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

{

    E[cnt].v=v,E[cnt].w=w,E[cnt].next=head[u];

    head[u]=cnt++;

    E[cnt].v=u,E[cnt].w=w,E[cnt].next=head[v];

    head[v]=cnt++;

}

int find(int x)

{

    return x==f[x]?x:f[x]=find(f[x]);

}

void tarjan(int root)

{

    vis[root]=;

    f[root]=root;//初始化

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

    {

        if (P[i].X==root&&vis[P[i].Y])

            Lca[i]=find(P[i].Y);

        if (P[i].Y==root&&vis[P[i].X])

            Lca[i]=find(P[i].X);

    }

    for (int i=head[root]; i!=-; i=E[i].next)

    {

        if (!vis[E[i].v])

        {

            dis[E[i].v]=dis[root]+E[i].w;

            tarjan(E[i].v);

            f[E[i].v]=root;

        }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while (T--)

    {

        init();

        int a,b,c;

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

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

        {

            scanf("%d%d%d",&a,&b,&c);

            addedge(a,b,c);

        }

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

        scanf("%d%d",&P[i].X,&P[i].Y);

        dis[]=;

        tarjan();

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

        printf("%d\n",dis[P[i].X]+dis[P[i].Y]-*dis[Lca[i]]);

    }

    return ;

}

相关文章