HDU 2586.How far away?

272


题目



点击显/隐题目

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.


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.


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


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


10
25
100
100




题解



倍增最近公共祖先模板题

代码


点击显/隐代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

#define Log(format, ...) // printf(format, ##__VA_ARGS__)

const int maxn = 40005;
const int maxlog = 17;

int n, m;

struct Edge {
    int c, w;
    Edge(int _c = 0, int _w = 0) : c(_c), w(_w) {}
};

vector<Edge> edges[maxn];

void addEdge(int u, int v, int w) {
    Log("addEdge(%d,%d,%d)\n", u, v, w);

    edges[u].push_back(Edge(v, w));
    edges[v].push_back(Edge(u, w));
}

int depth[maxn];
int parent[maxn][maxlog];
int weight[maxn][maxlog];

void lca() {
    for (int j = 1; j < maxlog; ++j) {
        for (int i = 1; i <= n; ++i) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
            weight[i][j] = weight[i][j - 1] + weight[parent[i][j - 1]][j - 1];
        }
    }
}

int query(int a, int b) {
    Log("Log(%d,%d)\n", a, b);

    int ans = 0;
    if (depth[a] < depth[b])
        swap(a, b);
    while (depth[a] != depth[b]) {
        int dis = depth[a] - depth[b];
        int step = (int)(log(dis) / log(2));
        Log("\t%d->%d (%d)\n", a, parent[a][step], weight[a][step]);
        ans += weight[a][step]; // 由于这里还要用到a,因此a要在后面再赋值
        a = parent[a][step];
    }
    Log("\tthe same depth %d %d\n", a, b);
    while (a != b) {
        int step = 0;
        for (int i = 0; i < maxlog; ++i) {
            if (parent[a][i] == parent[b][i]) {
                step = i - (i ? 1 : 0);
                break;
            }
        }
        Log("\tstep: %d a: %d->%d (%d)  b: %d->%d (%d)\n", step, a,
            parent[a][step], weight[a][step], b, parent[b][step],
            weight[b][step]);
        ans += weight[a][step] + weight[b][step];
        a = parent[a][step];
        b = parent[b][step];
    }
    return ans;
}

void dfs(int t, int deep) {
    depth[t] = deep;
    for (auto edge : edges[t]) {
        int child = edge.c;
        if (parent[t][0] != child) {
            parent[child][0] = t;
            weight[child][0] = edge.w;
            dfs(child, deep + 1);
        }
    }
}

void init() {
    memset(parent, 0, sizeof(parent));
    for (int i = 0; i <= n; ++i) {
        edges[i].clear();
    }
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        init();

        for (int i = 1; i < n; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            addEdge(u, v, w);
        }

        dfs(1, 0);
        lca();

        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            cout << query(a, b) << endl;
        }
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论