http://acm.hdu.edu.cn/showproblem.php?pid=2586
How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21250 Accepted Submission(s): 8368
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
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
题目大意：给一个有权树，有Q次询问，求任意两点的距离。
题目分析：在树中有一个性质：任意两点的距离 ANS = dist[ u ] + dist[ v ] - dist[ lca(u,v) ]，其中dist[ I ]是根到 I 的 距离 ，由于需要多次询问，所以使用Tarjan离线求LCA比较快
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=;
struct edge{
int to;
int len;
};
vector<struct edge>G[maxn];
vector<int>qury[maxn];
vector<int>num[maxn];
int dis[maxn],vis[maxn],ans[maxn],fa[maxn];
void init()
{
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
for(int i = ; i < ; i++)
{
G[i].clear();
qury[i].clear();
num[i].clear();
fa[i]=i;
}
}
int find(int x)
{
int xx=x;
while(fa[x]!=x)
{
x=fa[x];
}
while(fa[xx]!=x)
{
int t=fa[xx];
fa[xx]=x;
xx=t;
}
return x;
}
void Union(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy);
fa[yy]=xx;//在完成子节点的Tarjan遍历之后，把子节点纳入父节点名下
}
void Tarjan(int u,int ll)
{
vis[u]=;
dis[u]=ll;
for(int i = ; i< G[u].size() ;i++)
{
struct edge wqw=G[u][i];
if(vis[wqw.to])continue;
Tarjan(wqw.to,wqw.len+ll);
Union(u,wqw.to);
}
for(int i = ; i < qury[u].size() ; i++)
{
if(vis[qury[u][i]])
{
ans[num[u][i]]=dis[u]+dis[qury[u][i]]-*dis[find(qury[u][i])];
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i = ; i < n ; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
G[a].push_back((struct edge){b,c});
G[b].push_back((struct edge){a,c});
}
for(int i = ; i < m ; i++)
{
int a,b;
scanf("%d%d",&a,&b);
qury[a].push_back(b);
qury[b].push_back(a);
num[a].push_back(i);
num[b].push_back(i);
}
Tarjan(,);
for(int i = ; i < m ; i++)
{
printf("%d\n",ans[i]);
}
}
return ;
}