How far away ？
Tarjan
http://www.cnblogs.com/caiyishuai/p/8572859.html
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20491 Accepted Submission(s):
8010
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.
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.
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.
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
Source
Recommend
这一道题目意思是说，村庄之间有路可达，给你N个节点，N-1条路，然后M组查询，查询两个节点之间的距离。
N个节点N-1条边，那么就符合树的定义。所以题目给的就是一个树，就是求树上两个节点的距离。
这一道题目可以和LCA联系起来，求两个节点（a和b）的距离。两个节点必然由一个公共点连接起来，这个点就是LCA（最近公共祖先c）
那么求距离就可以转换为a到根节点的距离+b到根节点的距离—c到根节点的距离—c到根节点的距离。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define N 100000+10
using namespace std;
int n,m;
struct node
{
int to,next,cost;
}e[N];
int cnt;
int fa[][N];
int head[N],depth[N],dis[N];
void init()
{
memset(head,-,sizeof head);
memset(depth,,sizeof depth);
memset(dis,,sizeof dis);
cnt=;
}
void addedge(int u,int v,int w)//建图过程，建双向边
{
e[cnt].to=v;
e[cnt].cost=w;
e[cnt].next=head[u];
head[u]=cnt++;
} void DFS(int u,int f)//遍历树
{
fa[][u]=f;
for(int i=head[u];~i;i=e[i].next)//遍历所有相连的边
{
int To=e[i].to;
if(To!=f)//去掉以后MLE，可能是递归求的过程中太多临时变量
{//建树过程建双向边，会出现to=f的情况，去掉以后会陷入无限递归中
dis[To]=dis[u]+e[i].cost;//更新距离
depth[To]=depth[u]+;//更新深度
DFS(To,u);
}
} } void solve()
{
depth[]=;//题目给的是一个树
dis[]=;//无论怎么样的树，都可以把1视为根节点
DFS(,-);
for(int i=;i<;i++)//树上倍增
for(int j=;j<=n;j++)
fa[i][j]=fa[i-][fa[i-][j] ];
} int LCA(int u,int v)//求最近公共祖先
{
if(depth[u]>depth[v])//保证V的深度比较大
swap(u,v);
for(int i=;i<;i++)//倍增到深度相同
if((depth[v]-depth[u])>>i&)//二进制特性，一定能跳到深度相同
v=fa[i][v];
if(u==v)
return u;
for(int i=;i>=;i--)//两者同时倍增
{
if(fa[i][u]!=fa[i][v])
{
u=fa[i][u];
v=fa[i][v];
}
}
return fa[][v];
}
int main()
{
int i,t;
int a,b,c;
while(scanf("%d",&t)!=EOF)
{ while(t--)
{
init();
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
solve();
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
int ans=dis[a]+dis[b]-*dis[LCA(a,b)];
printf("%d\n",ans);
}
}
return ;
}
}