Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
Source
ECJTU 2009 Spring Contest
Recommend
lcy | We have carefully selected several similar problems for you: 3486 2874 2888 3234 2818
剛接觸最近公共祖先，對這個題還沒有什麼思路，，而且，，我還以為是求最短路類。。。hhh 加油吧~
完全是看這篇部落格學習的，原來vector用起來這麼友善
https://blog.csdn.net/nameofcsdn/article/details/52230548
dfs序->RMQ->LCA
/*
翻譯：
有 n個房子，一些雙向路連接配接他們，人們都喜歡問，如果我想到
A->B 需要多遠，答案唯一
n個房子，m條詢問
n-1行是代表 i->j 需要k
求詢問兩個home的最小距離。
這是 lca 嗎 怎麼那麼像最短路。。。才識尚淺呀~~
LCA RMQ ST
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <set>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define maxx 44000
int n,m;
struct Edge
{
int to,diss;
};
vector <Edge> v[maxx];
int dep[maxx];//每一點的深度
int visnum[maxx<<2];//周遊數組（dfs序）2*n-1 周遊的點
int visn[maxx];//周遊點的周遊數
int vnum;
int mins[maxx<<2][20];//RMQ利用dp在求區間最小值
int dist[maxx];//每點到祖先的距離diss
int fa[maxx];
void dfs(int u,int d,int dis)//dfs序
{//u點 深度 距離
vector<Edge>::iterator p;
dep[u]=d;
dist[u]=dis;
for(p=v[u].begin();p!=v[u].end();p++)//突然，，，感覺用 vector 真友善诶。。
{
if(fa[(*p).to]>-1) continue;
fa[(*p).to]=u;
visnum[vnum++]=u;//存入通路的第vnum個點是哪個點
dfs((*p).to,d+1,dis+(*p).diss);
}
visn[u]=vnum;
visnum[vnum++]=u;
}
void RMQ()//Range Minimum/Maximum Query區間查詢最值 ST算法
{
for(int i=1;i<=2*n-1;i++) mins[i][0]=visnum[i];//初始
for(int j=1;(1<<j)<=2*n-1;j++)
{
for(int i=1;i+(1<<j)-1<=2*n-1;i++)
{
int mid=i+(1<<(j-1));//把區間分成長度相同的兩段
if(dep[mins[i][j-1]]<dep[mins[mid][j-1]])
mins[i][j]=mins[i][j-1];
else mins[i][j]=mins[mid][j-1];
}
}
}
int lca(int x,int y)//求x,y的最近公共祖先
{
x=visn[x];
y=visn[y];
if(x>y) swap(x,y);
int j=0;
while((1<<j)<=y-x+1) j++;//在len=y-x+1分成長度為（1<<j）區間
j--;
int minn=mins[y+1-(1<<j)][j];
if(dep[minn]>dep[mins[x][j]])
minn=mins[x][j];
return minn;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int a,b,c,x,y;
cin>>n>>m;
vnum=1;
for(int i=1;i<=n;i++)
{
v[i].clear();
fa[i]=-1;
}
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
//借助vector建邊
Edge e1,e2;
e1.diss=c,e1.to=b;
v[a].insert(v[a].end(),e1);
e2.diss=c,e2.to=a;
v[b].insert(v[b].end(),e2);
}
fa[1]=1;
dfs(1,1,0);
RMQ();
while(m--)
{
cin>>x>>y;
cout<<dist[x]+dist[y]-2*dist[lca(x,y)]<<endl;
}
}return 0;
}
還有一種 方法是 我在HDU 網站讨論區看的，隻使用了 dfs ，有n個房子，n-1條邊，深搜的話是一定能搜到的。果然……越簡單的方法越容易被遺忘，不過這個題資料有點水， 如果資料很大，直接用 dfs 就爆了 ，就不太适用了……
不管怎麼樣，貼個代碼吧……因為dfs，bfs太弱了 (Ｔ▽Ｔ)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <set>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define maxx 44000
struct Edge
{
int to,diss;
}edge;
vector <Edge> mapp[maxx];//相當于二維數組，第一維size為maxx，第二維無限
int vis[maxx];
int flag;//判斷是否找到終點
int n,m;
int st,en;
void dfs(int t,int dis)
{
if(mapp[t].empty())//
return ;
if(t==en)
{
flag=1;
cout<<dis<<endl;
return ;
}
for(int j=0;j<mapp[t].size();j++)
{
if(!vis[mapp[t][j].to])
{
vis[mapp[t][j].to]=1;
dfs(mapp[t][j].to,dis+mapp[t][j].diss);
vis[mapp[t][j].to]=0;
}
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int a,b,c,x,y;
cin>>n>>m;
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
edge.to=b,edge.diss=c;
mapp[a].push_back(edge);
edge.to=a,edge.diss=c;
mapp[b].push_back(edge);
}
for(int i=1;i<=m;i++)
{
memset(vis,0,sizeof(vis));
flag=0;
cin>>st>>en;
vis[st]=1;
dfs(st,0);
}
for(int i=0;i<n;i++)
mapp[i].clear();
}return 0;
}
Other:Tarjan
/*
Tarjan(u)//marge 和 find 為并查集 合并函數和查找函數
{
for each(u,v)//通路u的所有子節點
{
Tarjan(v);//繼續往下周遊
marge(u,v);//合并v到u上
标記v被放通路過;
}
for each(u,e)//通路所有和u有詢問關系的e
{
如果e被通路過，
u,e的最近公共祖先為find(e);
}
}
Tarjan是離線算法，
離線算法是 統一輸入後再統一輸出，而不是邊輸入邊實時輸出
算法複雜度O(n+q) q為查詢次數
*/
#pragma comment (linker,"/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#define ll long long
#define inf 0x3f3f3f3f
#define maxx 44000
using namespace std;
int cnt,n,m;
int fa[maxx],x[maxx],y[maxx],z[maxx];
int dis[maxx],vis[maxx],head[maxx];
struct Edge
{
int to,next,diss;
}edge[maxx<<1];
void add_edge(int u,int v,int val)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].diss=val;
head[u]=cnt++;
}
int Find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=Find(fa[x]);
}
void tarjan(int u)
{
vis[u]=1;
fa[u]=u;
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(vis[edge[i].to]==0)
{
dis[edge[i].to]=dis[u]+edge[i].diss;
tarjan(edge[i].to);
fa[edge[i].to]=u;
}
}
for(int i=1;i<=m;i++)
{
if(vis[y[i]]&&x[i]==u) z[i]=Find(y[i]);
if(vis[x[i]]&&y[i]==u) z[i]=Find(x[i]);
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int a,b,c;
cin>>n>>m;
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
add_edge(a,b,c);
add_edge(b,a,c);
}
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(z,0,sizeof(z));
for(int i=1;i<=m;i++)
cin>>x[i]>>y[i];
dis[1]=0;
memset(vis,0,sizeof(vis));
tarjan(1);
for(int i=1;i<=m;i++)
{
cout<<dis[x[i]]+dis[y[i]]-2*dis[z[i]]<<endl;
}
}return 0;
}
![[HDU] 3549 Flow Problem [最大流][Dinic][讀取優化][圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)