链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2586
题目：
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.
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.
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
题意：
给你t个测试样例，每个测试样例开头给你一组n m，n个点，m条询问，然后是n-1条边u v w，u和v之间的路径长度为w，最后是m条询问，问你u v之间的距离。
思路：
dfs一遍求出每个点到树根的距离，然后求出u和v的lca，两个点的距离就是cost[u] + cost[v] - 2 * cost[lca(u,v)]。
实现：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
void read(
int &x){ x=
0;
char c=getchar();
while(c<
'0' || c>
'9')c=getchar();
while(c>=
'0' && c<=
'9'){ x=x*
10+c-
'0';c=getchar(); }}
void write(
int x){
int y=
10,len=
1;
while(y<=x) {y*=
10;len++;}
while(len--){y/=
10;
putchar(x/y+
48);x%=y;}}
using namespace std;
const int maxn =
40007;
int n, m, up[maxn][
37], dep[maxn], _, cost[maxn];
bool vis[maxn];
vector<pair<int, int> > edge[maxn];
void addedge(
int u,
int v,
int w) {
edge[u].emplace_back(v,w);
edge[v].emplace_back(u,w);
}
void dfs(
int u,
int d) {
dep[u] = d; vis[u] =
true;
for(
auto i : edge[u]) {
int v = i.first;
if (!vis[v]) {
cost[v] = cost[u] + i.second;
dfs(v, d +
1);
up[v][
0] = u;
}
}
}
void process() {
for(
int j=
1 ; j<
31 ; j++)
for(
int i=
1 ; i<=n ; i++)
if(up[i][j-
1] != -
1)
up[i][j] = up[up[i][j-
1]][j-
1];
}
int lca(
int u,
int v) {
if(dep[u] < dep[v]) swap(u,v);
int tmp = dep[u] - dep[v];
for(
int j=
0 ; j<
31 && dep[u] != dep[v] ; j++) {
if(tmp & (
1<<j))
u = up[u][j];
}
if(u == v)
return v;
for(
int j =
30 ; j>=
0 ; j--) {
if(up[u][j] != up[v][j])
u = up[u][j], v = up[v][j];
}
return up[u][
0];
}
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
#endif
read(_);
while(_--!=
0) {
read(n),read(m);
memset(dep, -
1,
sizeof dep);
memset(up, -
1,
sizeof up);
memset(vis,
0,
sizeof vis);
memset(cost,
0,
sizeof cost);
for(
int i=
1, u, v, w ; i<n ; i++) {
read(u),read(v),read(w);
addedge(u,v,w);
}
dfs(
1,
1);
process();
for(
int i=
0, u, v ; i<m ; i++) {
read(u),read(v);
int tmp = lca(u,v);
write(cost[u]+cost[v]-cost[tmp]-cost[tmp]);
cout <<
'\n';
}
for(
int i=
0 ; i<=n ; i++) edge[i].clear();
}
return 0;
}
