HDOJ 2586 How far away?
今天感冒了，热天感冒实在是不幸啊，不过这道题倒是很听话一交就过。还是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;}