HDU 2586-How far away（最近公共祖先LCA）

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=2586

大緻題意：給你一棵樹，樹上有n個點，n-1條邊，有q次查詢，每次查詢樹上任意兩點間的距離。

題解：LCA經典題，定義一個dis數組表示該點到樹根（假如有根的話）的距離，則根據LCA中的

Tarjan算法的工作機制和原理，儲存查詢的兩點，之後跑一發Tarjan，有關系（其中待求的兩點）

的兩點，假如另一點已經通路，則找到這兩點的最近公共祖先，很容易推出，這兩點間的距離就是

dfs[ i ]+dis[ j ]-2*dis[ z[i] ];其中z[i]為i和j的最近公共祖先。

拓展：最近公共祖先及Tarjan算法講解

#include<map>  
#include<stack>  
#include<queue>  
#include<vector>  
#include<math.h>  
#include<stdio.h>  
#include<iostream>  
#include<string.h>  
#include<stdlib.h>  
#include<algorithm>  
using namespace std;  
typedef long long  ll;  
#define inf 1000000000  
#define mod 1000000007   
#define  maxn  40010  
#define  lowbit(x) (x&-x)  
#define  eps 1e-10  
int dis[maxn],vis[maxn],n,m,e1[maxn],e2[maxn],fa[maxn],e3[maxn];
//e1和e2數組分别存待求的兩點，e3存這兩點的最近公共祖先
struct node
{
	int id,c;
};
vector<node>q[maxn];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void tarjan(int x)
{
	int i;
	vis[x]=1;fa[x]=x;
	for(i=1;i<=m;i++)
	{
		if(e1[i]==x && vis[e2[i]])
			e3[i]=find(e2[i]);
		if(e2[i]==x && vis[e1[i]])
			e3[i]=find(e1[i]);
	}
	for(i=0;i<q[x].size();i++)
	{
		node v=q[x][i];
		if(vis[v.id])
			continue;
		dis[v.id]=dis[x]+v.c;
		tarjan(v.id);
		fa[v.id]=x;
	}
}
int   main(void)
{
	node tmp;
	int T,i,x,y,z;
	scanf("%d",&T);
	while(T--)
	{
		memset(e1,0,sizeof(e1));
		memset(e2,0,sizeof(e2));
		memset(e3,0,sizeof(e3));
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		scanf("%d%d",&n,&m);
		for(i=1;i<n;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			tmp.id=x;tmp.c=z;
			q[y].push_back(tmp);
			tmp.id=y;tmp.c=z;
			q[x].push_back(tmp);
		}
		for(i=1;i<=m;i++)
			scanf("%d%d",&e1[i],&e2[i]);
		dis[1]=0;//預設1為樹根
		tarjan(1);
		for(i=1;i<=m;i++)
			printf("%d\n",dis[e1[i]]+dis[e2[i]]-2*dis[e3[i]]);
		for(i=0;i<=maxn;i++)
			if(q[i].empty()==0)
				q[i].clear();
	}
	return 0;
}