学步园

       今天感冒了，热天感冒实在是不幸啊，不过这道题倒是很听话一交就过。还是Tarjan算法实现离线的询问，原来讲LCA推荐了一个博客，像这种图其实条件中给出了要求，没有环的无向图不就是树吗，询问这么多，一看就知道是LCA了，我只学过Tarjan的离线算法，用它来练练手。首先人清楚一点，这里是求距离，假设u,v的祖先是a，那么（u到根节点的距离）+（v到根节点的距离）-2*（a到根节点的距离）=（u到v的距离）。所以在DFS的时候顺便算出到根节点的距离存储在dist数组中，根节点可以任选（无向树上任意结点都可以做根结点）。

代码：

#include<iostream>
#include<string.h>
using namespace std;
struct Edge
{
       int v,w,next;
} e[80005],qe[500];
bool visit[40005];
int dist[40005],f[40005],size,qsize;
int head[40005],qhead[40005];
void AddEdge(int a,int b,int c)
{
     e[size].v=b;
     e[size].w=c;
     e[size].next=head[a];
     head[a]=size++;
     e[size].v=a;
     e[size].w=c;
     e[size].next=head[b];
     head[b]=size++;
}
void AddQedge(int a,int b)
{
     qe[qsize].v=b;
     qe[qsize].next=qhead[a];
     qhead[a]=qsize++;
     qe[qsize].v=a;
     qe[qsize].next=qhead[b];
     qhead[b]=qsize++;
}
void init()
{
     size=0; qsize=0;
     memset(e,0,sizeof(e));
     memset(qe,0,sizeof(qe));
     memset(head,-1,sizeof(head));
     memset(qhead,-1,sizeof(qhead));
     memset(f,0,sizeof(f));
     memset(dist,0,sizeof(dist));
     memset(visit,false,sizeof(visit));
}
int Find(int x)
{
    if( x!=f[x])
        f[x]=Find(f[x]);
    return f[x];
}
void Tarjan(int u)
{
     f[u]=u;
     visit[u]=true;
     int i,v;
     for( i=head[u]; i!=-1; i=e[i].next){
          int v=e[i].v;
          if( !visit[v]){
              dist[v]=dist[u]+e[i].w;
              Tarjan(v);
              f[v]=u;
          }
     }
     for( i=qhead[u]; i!=-1; i=qe[i].next){
          int v=qe[i].v;
          if( visit[v]){
              qe[i].w=dist[u]+dist[v]-2*dist[Find(v)];//将算得的距离存储在w上
              qe[i^1].w=qe[i].w;
          }
     }         
}
int main()
{
    int n,m,t,i,a,b,c;
    scanf("%d",&t);
    while( t--){
           scanf("%d%d",&n,&m);
           init();
           n-=1;
           while( n--){
                scanf("%d%d%d",&a,&b,&c);
                AddEdge(a,b,c);
           }
           for( i=0; i<m; i++){
                  scanf("%d%d",&a,&b);
                  AddQedge(a,b);
           }
           Tarjan(1);//选1做跟结点，求其它结点到根节点的距离。
           for( i=0; i<qsize; i+=2)
                printf("%d\n",qe[i].w);
    }            
    return 0;
}