题目

{% fold 点击显/隐题目 %}

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
{% endfold %}

题解

倍增最近公共祖先模板题

代码

{% fold 点击显/隐代码 %}```cpp How far away? https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
#include
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 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;

}

{% endfold %}