# CodeStream

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
 12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks

# 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

10
25
100
100

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 set[max_size], d[max_size], ans[201];
bool fals[max_size];

struct Edge
{

int v;

int w;

int pre;
}

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
= cnt++;
}

{
= y;
= cast;
= next[x];
next[x]
= cnt++;
}

void Tarjan(int k)
{
fals[k]
= true;

int i, x, root;

for (i = next[k]; i != 0; i = ask[i].pre)

{
x

if (!fals[x])continue;
root
= find(x);
= 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++)

{
= next[i] = 0;

set[i] = i;
fals[i]
= false;
}

cnt
= 1;

for (i = 1; i < n; i++)

{
scanf(
"%d%d%d"&x, &y, &z);
}

cnt
= 1;

for (i = 1; i <= m; i++)

{
scanf(
"%d%d"&x, &y);
}

d[
1= 0;
Tarjan(
1);

for (i = 1; i <= m; i++)
printf(
"%d\n", ans[i]);
}

return 0;
}
posted on 2011-03-24 15:44 CodeStream 阅读(573) 评论(0)  编辑 收藏 引用 所属分类: acm_LCA