CodeVs.1036 商务旅行 ( LCA 最近公共祖先 )
题意分析
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
首先用倍增处理树形结构，然后针对给出的M行城市编号，依次计算两两之间到LCA的距离，然后求和即为答案。
代码总览
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define nmax 100000
#define demen 25
using namespace std;
int fa[nmax][demen],dis[nmax],head[nmax],dep[nmax];
int n,m,tot = 0;
struct node{
int to;
int next;
int w;
}edge[nmax];
void add(int u, int v, int w){
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].w = w;
head[u] = tot++;
}
void dfs(int rt,int f){
fa[rt][0] = f;
for(int i = 1;i<=20;++i){
fa[rt][i] = fa[fa[rt][i-1]][i-1];
}
for(int i = head[rt];i!=-1;i = edge[i].next){
int nxt = edge[i].to;
if(nxt != f){
dis[nxt] = dis[rt] + edge[i].w;
dep[nxt] = dep[rt] + 1;
dfs(nxt,rt);
}
}
}
int lca(int x, int y){
int X = x,Y=y;
if(dep[x] < dep[y]) swap(x,y);
int dre = dep[x] - dep[y];
for(int i = 20;i>=0;--i){
if((1<<i) & dre)
x = fa[x][i];
}
if(x == y) return(abs(dis[X] - dis[Y]));
for(int i = 20;i>=0;--i){
if(fa[x][i] != fa[y][i]){
x = fa[x][i],y = fa[y][i];
}
}
return(dis[X]+dis[Y] - 2*dis[fa[x][0]]);
}
void init(){
memset(fa,0,sizeof fa);
memset(head,-1,sizeof head);
memset(dis, 0, sizeof dis);
memset(dep,0,sizeof dep);
tot = 0;
}
int main()
{
init();
int n,u,v,w;
scanf("%d",&n);
for(int i = 0;i<n-1;++i){
scanf("%d %d",&u,&v);
add(u,v,1);
add(v,u,1);
}
dep[1] = 1;
dfs(1,0);
int k = 0,ans = 0;
scanf("%d",&k);
scanf("%d",&u);
for(int i = 0;i<k-1;++i){
scanf("%d",&v);
ans+=lca(u,v);
swap(u,v);
}
printf("%d\n",ans);
return 0;
}