题目
Description
2000MS/65536K
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.
Simple input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Simple output
10
25
100
100
题目分析
这个题其实可以用最短路来做，但是我们这里用LCA。大意是在一个村庄里面有n栋房子和n-1条路给出这m条路的距离，再给出m个询问，你的程序需要对每个询问进行答复，回答出查询的路线的距离。先建立好边并标上边权，子树若无询问过就加上自己到询问的距离，最后输出即可。
AC代码
7996K/31MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
struct nod
{
int v;///当前边序号
int dis;///边权
int next;
};
nod edge[maxn];
int dis[maxn],s[maxn],e[maxn];
///dis,s,e分别保存距离起点和终点;
int pre[maxn],lca[maxn],r[maxn];
///pre,lca,r分别代表父亲数组,e和s的LCA,先祖数组
int m,n,top;
bool vis[maxn];
int add_edge(int u,int v,int val)
{
edge[top].v=u;
edge[top].dis=val;
edge[top].next=pre[v];
pre[v]=top++;
edge[top].v=v;
edge[top].dis=val;
edge[top].next=pre[u];
pre[u]=top++;
return 0;
}
int inil()
{
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
memset(r,0,sizeof(r));
top=0;
return 0;
}
int findset(int x)
{
if(x!=r[x])
{
r[x]=findset(r[x]); ///路径压缩
}
return r[x];
}
void tarjan(int k)
{
vis[k]=true;///标记k树已经被扫描过
r[k]=k;///让k自己的根节点为自己
for(int i=1; i<=m; i++)
{
if(s[i]==k&&vis[e[i]])///如果s[i]与k节点相等且e[i]已经被扫描过
lca[i]=findset(e[i]);///则寻找e[i]的先祖节点
if(e[i]==k&&vis[s[i]])///反之则寻找s[i]的先祖节点
lca[i]=findset(s[i]);
}
for(int i=pre[k]; i!=-1; i=edge[i].next)
{
if(!vis[edge[i].v])
{
dis[edge[i].v]=dis[k]+edge[i].dis;
tarjan(edge[i].v);
r[edge[i].v]=k;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b,c;
scanf("%d%d",&n,&m);
inil();
for(int i=1; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
}
for(int i=1; i<=n; i++)
{
s[i]=0;
e[i]=0;
lca[i]=0;
}
for(int i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
s[i]=a;
e[i]=b;
}
memset(vis,false,sizeof(vis));
dis[1]=0;
tarjan(1);
for(int i=1; i<=m; i++)
{
printf("%d\n",dis[s[i]]+dis[e[i]]-2*dis[lca[i]]);
}
}
}