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
(LCA模闆題參考部落格：https://blog.csdn.net/Viscu/article/details/70141399
https://blog.csdn.net/qq_41955236/article/details/81516380
https://www.cnblogs.com/lsdsjy/p/4071041.html
)
1.tarjan+離線處理
（給詢問建圖沒想到，巧妙的處理了離線詢問，詳情看注釋）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#define LL long long
using namespace std;
const int maxn=4e4+10;
bool vis[maxn];
int dis[maxn],f[maxn],head[maxn],lca[420],cnt;
//存圖
struct node
{
int to,w;
node(){}
node(int to,int w):to(to),w(w){}
};
//給詢問建圖
struct Node
{
int u,v;
int id;//用來存是第幾個詢問
int next;
}que[420];
vector<node> ve[maxn];
//建詢問圖加邊
void add(int u,int v,int w)
{
que[cnt].u=u;
que[cnt].v=v;
que[cnt].id=w;
que[cnt].next=head[u];
head[u]=cnt++;
}
//并查集維護
int getf(int x)
{
return f[x]==x?x:f[x]=getf(f[x]);
}
//tarjan算法
void tarjan(int u,int fa)
{
for(int i=0;i<ve[u].size();i++)
{
int v=ve[u][i].to;
if(v==fa) continue;
//根到目前節點的距離
dis[v]=dis[u]+ve[u][i].w;
tarjan(v,u);
//把u的子樹合并到u上
f[getf(v)]=u;
}
//标記已周遊
vis[u]=1;
//處理詢問
for(int i=head[u];i!=-1;i=que[i].next)
{
//如果v被周遊過，那麼與u的LCA就是v的目前祖先
if(vis[que[i].v])
{
lca[que[i].id]=getf(que[i].v);
}
}
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
cnt=0;
scanf("%d%d",&n,&m);
//初始化
for(int i=1;i<=n;i++)
{
ve[i].clear();
dis[i]=0;
vis[i]=0;
f[i]=i;
head[i]=-1;
}
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
ve[u].push_back(node(v,w));
ve[v].push_back(node(u,w));
}
//建詢問圖
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
}
tarjan(1,0);
//建圖的時候對于同一個詢問建了兩條邊，是以i+=2
for(int i=0;i<cnt;i+=2)
{
int u,v,id;
u=que[i].u;
v=que[i].v;
id=que[i].id;
printf("%d\n",dis[u]+dis[v]-2*dis[lca[id]]);
}
}
return 0;
}
2.樹上倍增(詳解看上方部落格)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#define LL long long
using namespace std;
const int maxn=4e4+10;
int dis[maxn],dep[maxn],f[maxn][25],lg[maxn],head[maxn],cnt;
bool vis[maxn];
int n,m;
//存圖
struct node
{
int to,w,next;
}ed[maxn<<1];
void add(int u,int v,int w)
{
ed[cnt].to=v;
ed[cnt].w=w;
ed[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int fa,int deep)
{
f[u][0]=fa;
dep[u]=deep;
vis[u]=1;
for(int i=head[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(vis[v]) continue;
dis[v]=dis[u]+ed[i].w;
dfs(v,u,deep+1);
}
return ;
}
int LCA(int x,int y)
{
//固定y，讓x向上走
if(dep[x]<dep[y]) swap(x,y);
//先讓兩個點走到相同深度
for(int i=20;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
//兩個節點共同向上走找LCA
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
cnt=0;
scanf("%d%d",&n,&m);
//初始化
for(int i=1;i<=n;i++)
{
vis[i]=0;
dis[i]=0;
head[i]=-1;
}
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,-1,1);
//預處理f數組，f[i][j]表示i節點向上走(1<<j)步後的節點的編号
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
}
}
return 0;
}
3.ST+RMQ
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=4e4+10;
struct node
{
int to,w,next;
}e[maxn<<1];
int n;
int head[maxn],ver[maxn<<1],R[maxn<<1],first[maxn],dis[maxn],cnt,tot;
//ver[i]:周遊編号為i的節點編号
//R[i]:周遊編号為i的節點的深度
//first[i]:節點i第一次被周遊時的編号
int dp[maxn<<1][25];//這裡要開2*n，因為周遊後的最大編号為2*n-1
//dp[i][j]:i~i+(1<<j)-1這個區間内深度最小的編号
bool vis[maxn];
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int fa,int dep)
{
vis[u]=1;
ver[++tot]=u;
first[u]=tot;
R[tot]=dep;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
dis[v]=dis[u]+e[i].w;
dfs(v,u,dep+1);
ver[++tot]=u;
R[tot]=dep;
}
}
}
void getST(int n)
{
for(int i=1;i<=n;i++)
dp[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
dp[i][j]=(R[a]<R[b]?a:b);
}
}
int RMQ(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)
k++;
int a=dp[l][k],b=dp[r-(1<<k)+1][k];
return (R[a]<R[b]?a:b);
}
int LCA(int u,int v)
{
int a=first[u],b=first[v];
if(a>b) swap(a,b);
int res=RMQ(a,b);
return ver[res];
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int m;
scanf("%d%d",&n,&m);
cnt=tot=0;
for(int i=1;i<=n;i++)
{
head[i]=-1;
dis[i]=0;
vis[i]=0;
}
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,0,1);
//2*n
getST(2*n-1);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
}
}
return 0;
}