HDU2586 How far away

LCA

题目

Description

2000MS/65536K
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.

Simple input

2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

Simple output

10
25
100
100

题目分析

这个题其实可以用最短路来做，但是我们这里用LCA。大意是在一个村庄里面有n栋房子和n-1条路给出这m条路的距离，再给出m个询问，你的程序需要对每个询问进行答复，回答出查询的路线的距离。先建立好边并标上边权，子树若无询问过就加上自己到询问的距离，最后输出即可。

AC代码

7996K/31MS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
struct nod
{
    int v;///当前边序号
    int dis;///边权
    int next;
};
nod edge[maxn];
int dis[maxn],s[maxn],e[maxn];
///dis,s,e分别保存距离起点和终点;
int pre[maxn],lca[maxn],r[maxn];
///pre,lca,r分别代表父亲数组,e和s的LCA,先祖数组
int m,n,top;
bool vis[maxn];
int add_edge(int u,int v,int val)
{
    edge[top].v=u;
    edge[top].dis=val;
    edge[top].next=pre[v];
    pre[v]=top++;
    edge[top].v=v;
    edge[top].dis=val;
    edge[top].next=pre[u];
    pre[u]=top++;
    return 0;
}
int inil()
{
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    memset(r,0,sizeof(r));
    top=0;
    return 0;
}
int findset(int x)
{
    if(x!=r[x])
    {
        r[x]=findset(r[x]); ///路径压缩
    }
    return r[x];
}
void tarjan(int k)
{
    vis[k]=true;///标记k树已经被扫描过
    r[k]=k;///让k自己的根节点为自己
    for(int i=1; i<=m; i++)
    {
        if(s[i]==k&&vis[e[i]])///如果s[i]与k节点相等且e[i]已经被扫描过
            lca[i]=findset(e[i]);///则寻找e[i]的先祖节点
        if(e[i]==k&&vis[s[i]])///反之则寻找s[i]的先祖节点
            lca[i]=findset(s[i]);
    }
    for(int i=pre[k]; i!=-1; i=edge[i].next)
    {
        if(!vis[edge[i].v])
        {
            dis[edge[i].v]=dis[k]+edge[i].dis;
            tarjan(edge[i].v);
            r[edge[i].v]=k;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c;
        scanf("%d%d",&n,&m);
        inil();
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add_edge(a,b,c);
        }
        for(int i=1; i<=n; i++)
        {
            s[i]=0;
            e[i]=0;
            lca[i]=0;
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            s[i]=a;
            e[i]=b;
        }
        memset(vis,false,sizeof(vis));
        dis[1]=0;
        tarjan(1);
        for(int i=1; i<=m; i++)
        {
            printf("%d\n",dis[s[i]]+dis[e[i]]-2*dis[lca[i]]);
        }

    }
}

题目链接

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