链接
How far away ？
Time Limit: 2000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 559 Accepted Submission(s): 218
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
Source
题目大意：
n个点，n-1条路形成了一棵树，然后又m个询问：(x,y)输出x到y的最短距离，典型的LCA问题，用Tarjan解决，时间复杂度为O(n+m)
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define max_size 40002
int cnt, head[max_size], next[max_size];
int set[max_size], d[max_size], ans[201];
bool fals[max_size];
struct Edge
{
int v;
int w;
int pre;
}eg[2*max_size], ask[404];
int find(int x)
{
if (x == set[x])
return x;
else
set[x] = set[set[x]];
return find(set[x]);
}
void add_edge(int x, int y, int z)
{
eg[cnt].v = y;
eg[cnt].w = z;
eg[cnt].pre = head[x];
head[x] = cnt++;
}
void add_ask(int x, int y, int cast)
{
ask[cnt].v = y;
ask[cnt].w = cast;
ask[cnt].pre = next[x];
next[x] = cnt++;
}
void Tarjan(int k)
{
fals[k] = true;
if (head[k] == 0)return ;
int i, x, root;
for (i = next[k]; i != 0; i = ask[i].pre)
{
x = ask[i].v;
if (!fals[x])continue;
root = find(x);
ans[ask[i].w] = d[x] + d[k] - 2*d[root];
}
for (i = head[k]; i != 0; i = eg[i].pre)
{
x = eg[i].v;
if (fals[x])continue;
d[x] = d[k] + eg[i].w;
Tarjan(x);
x = find(x);
set[x] = k;
}
}
int main()
{
int i, m, n;
int x, y, z;
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
for (i = 0; i <= n; i++)
{
head[i] = next[i] = 0;
set[i] = i;
fals[i] = false;
}
cnt = 1;
for (i = 1; i < n; i++)
{
scanf("%d%d%d", &x, &y, &z);
add_edge(x, y, z);
add_edge(y, x, z);
}
cnt = 1;
for (i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
add_ask(x, y, i);
add_ask(y, x, i);
}
d[1] = 0;
Tarjan(1);
for (i = 1; i <= m; i++)
printf("%d\n", ans[i]);
}
return 0;
}