学步园

http://kmplayer.iteye.com/blog/604518

http://www.cnblogs.com/ylfdrib/archive/2010/11/03/1867901.html

在求解最近公共祖先为问题上，用到的是Tarjan的思想，从根结点开始形成一棵深搜树，非常好的处理技巧就是在回溯到结点u的时候，u的子树已经遍历，这时候才把u结点放入合并集合中，这样u结点和所有u的子树中的结点的最近公共祖先就是u了，

u和还未遍历的所有u的兄弟结点及子树中的最近公共祖先就是u的父亲结点。以此类推。。这样我们在对树深度遍历的时候就很自然的将树中的结点分成若干的集合，两个集合中的所属不同集合的任意一对顶点的公共祖先都是相同的，也就是说这两个集合的最近公共最先只有一个。对于每个集合而言可以用并查集来优化，时间复杂度就大大降低了，为O(n + q)，n为总结点数，q为询问结点对数。

从根开始深搜遍历树，每当回溯到一个节点时，那就意味着我们已经完成了该节点子树的遍历，显然这个节点就是子树中点以及其本身的最近公共祖先，以此类推到整个树。对于一个点，只有完成了其子树的遍历，我们才改变其 父节点 的值（赋初值为father[ i ] = i），这样，对于每次询问（就是给出两点标号，要求求出两点间最短距离，算一次询问。假设为 A 和 B），我们搜到 A （或B）时，如果 B （或A）已经被访问过，那么向上回溯，直到第一个 父节点
已经改变的点，就是包括点 A 和点 B 在内子树的根，这就是我们要找的 A 和 B 的最近公共祖先。

//parent为并查集，FIND为并查集的查找操作
//QUERY为询问结点对集合
//TREE为基图有根树
 Tarjan(u)
      visit[u] = true
      for each (u, v) in QUERY
          if visit[v]
              ans(u, v) = FIND(v)
      for each (u, v) in TREE    
          if !visit[v]
              Tarjan(v)
              parent[v] = u

/*
hdu 2586 最近公共祖先LCA
	不懂。。。 
	深搜遍历树，每当回溯到一个节点时，那就已经完成了该节点子树的遍历，
显然这个节点就是子树中点以及其本身的最近公共祖先，以此类推到整个树。
	对于一个点，只有完成了其子树的遍历，我们才改变其父节点的值..
设为 A 和 B，我们搜到A或B时，如果B或A已经被访问过，那么向上回溯，直到第一个父节点已经改变的点，
就是包括点A和点B在内子树的根，这就是我们要找的A和B的最近公共祖先。

*/
#include<iostream>
#include<stdio.h>
using namespace std;

#define N  40001 

struct Edge{  
    int bian,value;  
    int next;  
}edge[2*N]; 


int n,m,e_num,head[N];  
int x[N],y[N],z[N],pre[N],dist[N],vis[N]; 

void AddEdge(int a,int b,int c)//b->a  a->b
{  
    edge[e_num].bian=b; 
	edge[e_num].value=c; 
	edge[e_num].next=head[a];
	head[a]=e_num++; //a之前数量 
	
    edge[e_num].bian=a;
	edge[e_num].value=c; 
	edge[e_num].next=head[b]; 
	head[b]=e_num++;  
} 

int find(int x){  
    if(pre[x]!=x)  
        return pre[x]=find(pre[x]);  
    return pre[x];  
} 

void tarjan(int k)//从1开始 
{  
    int i;  
    vis[k]=1;   
    pre[k]=k; 
	 
    for(i=1;i<=m;i++)//m次询问,z[i]保存的是点x[i]和y[i]最近公共祖先
	{  
        if(x[i]==k&&vis[y[i]]) 
			z[i]=find(y[i]);  
        if(y[i]==k&&vis[x[i]]) 
			z[i]=find(x[i]);  
    } 
	 
    for(i=head[k];i!=-1;i=edge[i].next)//查找下一个 
	{  
        if(!vis[edge[i].bian])
		{  
            dist[edge[i].bian]=dist[k]+edge[i].value;  
            tarjan(edge[i].bian);  
            pre[edge[i].bian]=k;  
        }  
    }  
}

int main()
{
	int t,a,b,c,i;  
	
//	freopen("test.txt","r",stdin);
    scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		e_num=0;  
        memset(head,-1,sizeof(head));
        
		for(i=1;i<n;i++)
		{  
            scanf("%d%d%d",&a,&b,&c);  
            AddEdge(a,b,c);  
        } 
		
		for(i=1;i<=n;i++) 
            x[i]=y[i]=z[i]=0;  
        	
		for(i=1;i<=m;i++)
		{  
            scanf("%d%d",&a,&b);  
            x[i]=a; 
			y[i]=b;  
        } 
        
        memset(vis,0,sizeof(vis));  
        dist[1]=0;  
        tarjan(1);
        
        for(i=1;i<=m;i++)  
            printf("%d\n",dist[x[i]]+dist[y[i]]-2*dist[z[i]]);  
	}
	return 0;
}