題目連結： hdoj 2586
思路：
先找一點作為起點通過DFS回溯記錄每次DFS的點數（就是從根節點周遊所有點的去路和回來時的路）
用vis [ ] 數組記錄每次走過的是哪一個點--
用D [ ] 來對應vis [ ] 數組上的點的深度（與根節點的距離）
用R [ ] 來記錄每個點第一次出現的位置（兩點的最初位置之間（含他們自身）的點中深度最小的點就是他們的最近祖先）
然後查找RMQ算法就可以查到最近祖先了---
樣例：
我這個程式是讓n當根節點--（因為這一題讓1當根節點，，代碼錯的也會過--不便于學習新知識--（這題資料太弱））
看倒數第二行：回溯的順序就是13-10-12-10-7------
最後一行就是回溯的每個位置的點的深度（用RMQ時，就是根據這個比較的）
倒數第四行是每個點第一次出現的位置--
比如求3和4的最近祖先時：
3第一次出現在8的位置，4是18的位置--然後我們在最後一行8-18中找最小的深度（）
找到最小深度4--再看倒數第二行發現對應的是3----就是說明點3是3和4的最近祖先
回溯過程圖：
代碼上的中間值便于了解這個方法，是以就沒有删除--
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MA 420000
int n,m;
struct node{
int to,w,next;
}edge[MA*2];
int head[MA];
int D[MA];//深度
int R[MA];//每個點第一次出現的位置
int QM[MA][33];
int vis[MA*2],kp;//vis記錄第i個位置的數
int dis[MA];
void bfs(int now,int fa,int chang)
{
dis[now]=chang;
for (int j=head[now];j!=-1;j=edge[j].next)
{
if (edge[j].to==fa) continue;
bfs(edge[j].to,now,chang+edge[j].w);
}
}
void DFS(int now,int fa,int deep)
{
D[kp]=deep;
R[now]=kp;
vis[kp++]=now;
for (int j=head[now];j!=-1;j=edge[j].next)
{
if (edge[j].to==fa) continue;
DFS(edge[j].to,now,deep+1);
D[kp]=deep;
vis[kp++]=now;
}
}
int main()
{
int t;scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
int a,b,c;
for (int i=1;i<=n;i++)
head[i]=-1;
for (int i=0;i<n-1;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[i*2].to=b;edge[i*2].w=c;
edge[i*2].next=head[a];
head[a]=i*2;
edge[i*2+1].to=a;edge[i*2+1].w=c;
edge[i*2+1].next=head[b];
head[b]=i*2+1;
}
kp=1;
bfs(n,-1,0);
DFS(n,-1,1);
/* for (int i=1;i<=n;i++)
printf("%4d",i);printf("\n");
for (int i=1;i<=n;i++)
printf("%4d",R[i]);printf("\n");
for (int i=1;i<kp;i++)
printf("%4d",i);printf("\n");*/
for (int i=1;i<kp;i++)
{
// printf("%4d",vis[i]);
QM[i][0]=i;
}
/* printf("\n");
for (int i=1;i<kp;i++)
printf("%4d",D[i]);
printf("\n");*/
int nn=kp-1;
int p=log2(nn);
for (int i=1;i<=p;i++)
for (int j=1;j+(1<<i)-1<=nn;j++)
{
int aa=QM[j][i-1];
int bb=QM[j+(1<<(i-1))][i-1];
// printf("%d %d %d %d 66666666666\n",aa,bb,D[aa],D[bb]);
if (D[aa]<=D[bb])
QM[j][i]=aa;
else
QM[j][i]=bb;
// printf("%d %d %d\n",j,i,QM[j][i]);
}
/* printf("\n");
for (int i=1;i<=n;i++)
printf("%4d\n",dis[i]);
*/ while (m--)
{
scanf("%d%d",&a,&b);
int aa=min(R[a],R[b]);
int bb=max(R[a],R[b]);
// printf("%d %d 9999999999999\n",aa,bb);
int pp=log2(bb+1-aa);
int aaa=QM[aa][pp];
int bbb=QM[bb+1-(1<<pp)][pp];
// c=min(QM[aa][pp],QM[bb+1-(1<<pp)][pp]);
// printf("%d %d 666\n",aaa,bbb);
if (D[aaa]<=D[bbb])
c=aaa;
else
c=bbb;
// printf("%d\n",c);
c=vis[c];
// printf("ans : %d\n",dis[a]+dis[b]-2*dis[c]);
printf("%d\n",dis[a]+dis[b]-2*dis[c]);
}
}
return 0;
}
/*2
13 13
1 2 1
1 3 1
1 4 1
3 5 1
3 6 1
3 7 1
6 8 1
6 9 1
7 10 1
7 11 1
10 12 1
10 13 1*/