hdu 2586 How far away ？倍增LCA
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2586
思路：
- 针对询问次数多的时候，采取倍增求取LCA，同时跟新距离数组
- 因为
- \(2^{16} > 40000\)
- 所以所以表示祖先的数组dp[][]第二维取到16即可
- 就这道题来说，与比较tarjan比较，稍快一点
代码：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int maxn = 40005;
const int maxm = 80005;
struct node {
int to,next,w;
}edges[maxm];
int head[maxn],cnt,dp[maxn][17],dep[maxn],dist[maxn];
inline void addedge(int u, int v, int w) {
edges[cnt].to=v;
edges[cnt].w=w;
edges[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int s, int x) {
dp[s][0]=x;
dep[s]=dep[x]+1;
int t;
for(int i=1;(1<<i)<=dep[s];++i)
dp[s][i]=dp[dp[s][i-1]][i-1];
for(int i=head[s];i!=-1;i=edges[i].next) {
t=edges[i].to;
if(t==x) continue;
dist[t]=dist[s]+edges[i].w;
dfs(t,s);
}
}
inline int lca(int u, int v) {
if(dep[v]>dep[u]) swap(u,v);
for(int i=16;i>=0;--i) {
if((1<<i)<=(dep[u]-dep[v])) {
u=dp[u][i];
}
}
if(u==v) return u;
for(int i=16;i>=0;--i) {
if((1<<i)<=dep[u]&&(dp[v][i]!=dp[u][i])) {
u=dp[u][i];
v=dp[v][i];
}
}
return dp[u][0];
}
inline int slove(int u ,int v) {
int z=lca(u,v);
return dist[u]-2*dist[z]+dist[v];
}
inline void init() {
cnt=0;
memset(head,-1,sizeof(head));
}
int main() {
int t,n,m,u,v,w;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&n,&m);
init();
for(int i=1;i<n;++i) {
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dep[1]=0;//保持dfs的统一，实际dep[1]=1
dist[1]=0;
dfs(1,1);
for(int i=1;i<=m;++i) {
scanf("%d %d",&u,&v);
printf("%d\n",slove(u,v));
}
}
return 0;
}