411

# 题目

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) {

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;
}

dfs(1, 0);
lca();

for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
cout << query(a, b) << endl;
}
}
return 0;
}

• 点击查看/关闭被识别为广告的评论