How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20971 Accepted Submission(s): 8245
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.
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
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
25
100
100
思路：
Tarjan模板题,Tarjan还是比较好理解的。。。
推荐一篇很不错的博客：
https://www.cnblogs.com/JVxie/p/4854719.html
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e5+; struct node{
int to,next,w,sum;
};
int n,m,cnt1,cnt2;
node e[M<<]; //双向边
node q[M]; //询问的边
int fa[M],head[M<<],qhead[M];
bool vis[M];
ll d[M],res[M]; int find(int x){
return fa[x] == x?x:fa[x] = find(fa[x]);
} void add(int u,int v,int w){
e[++cnt1].w=w;e[cnt1].to=v;e[cnt1].next=head[u];head[u]=cnt1;
e[++cnt1].w=w;e[cnt1].to=u;e[cnt1].next=head[v];head[v]=cnt1;
} void add1(int u,int v){
q[++cnt2].to=v;q[cnt2].next=qhead[u];qhead[u]=cnt2;
} void dfs(int u,int fa,ll w){
d[u] = w;
for(int i = head[u];i!=-;i=e[i].next){
int v = e[i].to;
if(v==fa) continue;
dfs(v,u,w+e[i].w);
}
} void tarjan(int u){
fa[u] = u; vis[u] = ;
for(int i = head[u];i!=-;i=e[i].next){
int v = e[i].to;
if(!vis[v]){
tarjan(v);
fa[v] = u;
}
}
for(int i = qhead[u];i!=-;i=q[i].next){
int v = q[i].to;
if(vis[v]){
q[i].sum = find(v);
res[i] = d[u] + d[v] - *d[q[i].sum];//两者的距离
//cout<<i<<" "<<res[i]<<endl;
}
}
} void solve(){
for(int i = ;i < n;i ++) fa[i] = i;
memset(head,-,sizeof(head)); memset(qhead,-,sizeof(qhead));
memset(vis,,sizeof(vis));
cnt1 = cnt2 = ;
int u,v,w;
for(int i = ;i < n;i ++){
cin>>u>>v>>w;
add(u,v,w);
}
for(int i = ;i < m;i ++){
cin>>u>>v;
add1(u,v);
}
dfs(,-,);
tarjan();
} int main()
{
int t;
ios::sync_with_stdio();
cin.tie();cout.tie();
cin>>t;
while(t--){
cin>>n>>m;
solve();
for(int i = ;i <= m;i ++){
cout<<res[i]<<endl;
}
}
return ;
}