今天感冒了，熱天感冒實在是不幸啊，不過這道題倒是很聽話一交就過。還是Tarjan算法實現離線的詢問，原來講LCA推薦了一個博客，像這種圖其實條件中給出了要求，沒有環的無向圖不就是樹嗎，詢問這麼多，一看就知道是LCA了，我只學過Tarjan的離線算法，用它來練練手。首先人清楚一點，這裡是求距離，假設u,v的祖先是a，那麼（u到根節點的距離）+（v到根節點的距離）-2*（a到根節點的距離）=（u到v的距離）。所以在DFS的時候順便算出到根節點的距離存儲在dist數組中，根節點可以任選（無向樹上任意結點都可以做根結點）。
代碼：
[cpp]
#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;
}
