How far away
Time limit1000 ms
Memory limit32768 kB
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
解题心得：
- 题意就是给你一个双向图，每两点之间只有一条路径（其实就是一颗树），任意问你两点，要求输出两点间的最小距离。两种做法：
- 第一种就是直接跑暴力的dfs，复杂度也就是n*m最大8e6，很简单就跑过了。
- 第二种就是用LCA，两点之间最短的距离就是两点经过最近公共祖先形成的一条路。具体做法可以先预处理一下每个点到根节点的距离，存在数组dis里面，假如询问a，b之间的最小距离，就可以先得出最近公共祖先c然后答案就是dis[a] + dis[b] - 2*dis[c]。
- 然后就是双向边怎么建成一棵树的问题，可以用邻接表存图，存双向边，在使用的时候任意选一个点为根节点，使用过的点就标记上，这样就可以形成一棵树，因为每两点之间只选择一个方向的边。
dfs跑暴力：
#include<stdio.h>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 4e4+100;
bool vis[maxn],flag;
int n,m,ans,a,b;
vector <pair<int,int> > ve[maxn];
void init()
{
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++)
ve[i].clear();
for(int i=1;i<n;i++)
{
int a,b,len;
scanf("%d%d%d",&a,&b,&len);
//邻接表存图
ve[a].push_back(make_pair(b,len));
ve[b].push_back(make_pair(a,len));
}
}
void dfs(int pos,int sum_len)
{
if(vis[pos] || flag)
return ;
vis[pos] = true;
if(pos == b)
{
printf("%d
",sum_len);
flag = true;
return;
}
for(int i=0;i<ve[pos].size();i++)
{
pair<int,int> p;
p = ve[pos][i];
dfs(p.first,sum_len + p.second);
}
}
void solve()
{
while(m--)
{
flag = false;
memset(vis,0,sizeof(vis));
scanf("%d%d",&a,&b);
dfs(a,0);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
solve();
}
}LCA（tarjan写法）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e4+100;
vector <pair<int,int> > ve[maxn];
int vis[maxn],n,father[maxn],sum[maxn],m,a,b;
bool flag;
void init()
{
memset(father,0,sizeof(father));
memset(vis,0,sizeof(vis));
memset(sum,0,sizeof(sum));
for(int i=0; i<=n; i++)
ve[i].clear();
for(int i=1; i<n; i++)
{
int a,b,len;
scanf("%d%d%d",&a,&b,&len);
ve[a].push_back(make_pair(b,len));
ve[b].push_back(make_pair(a,len));
}
}
void dfs(int pos,int len)
{
vis[pos] = true;
sum[pos] = len;
for(int i=0; i<ve[pos].size(); i++)
{
int v = ve[pos][i].first;
if(!vis[v])
dfs(v,len+ve[pos][i].second);
}
return ;
}
int find(int x)
{
if(x == father[x])
return x;
return father[x] = find(father[x]);
}
void tarjan(int pos)//跑tarjan
{
vis[pos] = true;
father[pos] = pos;
if(flag)
return;
for(int i=0; i<ve[pos].size(); i++)
{
int v = ve[pos][i].first;
if(!vis[v])
{
tarjan(v);
father[v] = pos;
}
if(flag)
return ;
}
if(pos == a || pos == b)
{
if(pos != a)
swap(a,b);
if(father[b])
{
int ans = find(father[b]);
printf("%d
",abs(sum[a]+sum[b]-sum[ans]*2));
flag = true;
}
}
}
void query()
{
while(m--)
{
flag = false;
memset(father,0,sizeof(father));
memset(vis,0,sizeof(vis));
scanf("%d%d",&a,&b);
tarjan(1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
dfs(1,0);//先dfs预处理
query();
}
}