HDU【2586】How far away?（LCA）

Problem 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.

村裡有N棟房子，一些雙向的道路連接配接着它們。每天人們都喜歡這樣問：“如果我想從A房子到B房子要走多遠？”通常很難回答。但幸運的是，在這個村莊裡，答案總是唯一的，因為道路的修建方式是每兩棟房子之間都有一條唯一的簡單路徑（“簡單”意味着你不能兩次去一個地方）。你的任務是回答所有這些好奇的人。

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 by 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.

第一行是一個整數t（t<=10），表示測試用例的數量。

對于每個測試用例，第一行有兩個數字n（2<=n<=40000）和m（1<=m<=200）、房屋數量和查詢數量。下面的n-1行每一行由三個數字i、j、k組成，用空格隔開，表示有一條道路連接配接房屋i和房屋j，長度為k（0<k<=40000）。房屋的标簽從1到n。

接下來的m行中，每一行都有不同的整數i和j，你要回答i和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.

對于每個測試用例，輸出m行。每一行表示查詢的答案。在每個測試用例之後輸出一個空白行。

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

分析

Tarjan算法求最短路徑，兩點間的最短路徑可轉化為這兩個點分别到最近公共祖先的距離之和。

#include<iostream>
#include<vector>
using namespace std;
#define N 40000 + 10
#define M 200 + 10
int f[N],vis[N],sum[N],ans[M];
struct T {
    int v,w;
};
struct Q {
    int v,id;
};
vector<T> e[N];
vector<Q> q[N];
int find(int x)
{
    if(x != f[x]) f[x] = find(f[x]);
    return f[x]; 
}
void tarjan(int u,int s)
{
    sum[u] = s;
    vis[u] = 1;
    for(int i = 0; i < e[u].size(); i++) {
        int v = e[u][i].v;
        int w = e[u][i].w;
        if(!vis[v]) {
            tarjan(v,s + w);
            f[v] = u;
        }
    }
    for(int i = 0; i < q[u].size(); i++) {
        int v = q[u][i].v;
        if(vis[v]) {
            int k = q[u][i].id;
            int f = find(v);
            ans[k] = sum[u] + sum[v] - 2 * sum[f];
        }
    }
}
int main()
{
    int k;
    cin >> k;
    int n,m;
    while(k--) {
        cin >> n >> m;
        int u,v,w;
        for(int i = 1; i <= n; i++) { 
            e[i].clear();
            q[i].clear();
            f[i] = i;
            vis[i] = 0;
        }
        for(int i = 1; i < n; i++) {
            cin >> u >> v >> w;
            T t;
            t.v = v,t.w = w;
            e[u].push_back(t);
            t.v = u;
            e[v].push_back(t); 
        }
        for(int i = 0; i < m; i++) {
            cin >> u >> v;
            Q t;
            t.v = v,t.id = i;
            q[u].push_back(t);
            t.v = u;
            q[v].push_back(t);
        }
        tarjan(1,0);
        for(int i = 0; i < m; i++)
            cout << ans[i] << endl;
    }
    return 0;
}