HDU 2586 How far away ？【LCA模板题】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2586

题意：给你N个点，M次询问。1~N-1行输入点与点之间的权值，之后M行输入两个点（a,b）之间的最近距离；

思路：设d[maxn]是当前点到根结点的距离，则答案就是 d[a]-d[lca(a,b)]+d[b]-d[lca(a,b)]；

接下来介绍LCA（Least Common Ancestors）

即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

常见解法一般有三种

这里讲解一种在线算法—倍增

所谓倍增，就是按2的倍数来增大，也就是跳 1,2,4,8,16,321,2,4,8,16,32 …… 不过在这我们不是按从小到大跳，而是从大向小跳，即按……32,16,8,4,2,132,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。

首先我们定义fa[u][j]表示结点u的第2^j祖先

那么要怎么求出全部的fa数组呢

不难发现fa[u][0]就是u的父亲结点

这些父亲结点我们可以直接初始化

对于其他结点则有

f[u][j]=f[ fa[u][j-1] ] [j-1]

什么意思呢

u的第2^(j-1)祖先的第2^(j-1)祖先（2^(j-1)+2^(j-1)) 就是u的第2^j祖先

预处理各节点深度+初始化fa数组

void dfs(int x, int fa)
{
    h[x] = h[fa] + 1;
    f[x][0] = fa;
    for(int i = 1; (1 << i) <= h[x]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x]; i; i = edges[i].next)
    {
        if(edges[i].to != fa)
        {
            d[edges[i].to] = d[x] + edges[i].w;
            dfs(edges[i].to, x);
        }
    }
}

预处理之后怎么求解LCA(u，v)呢

我么先假定h[u]>h[v]

则两点深度差 d=h[u]-h[v]

现在我们要做的是把u升到与v同样的深度

while(h[x] > h[y])
        x = f[x][lg[h[x] - h[y]] - 1];//因为预处理的log函数是log2(i)+1所以要-1

对于任意一个d

我们都能将其分解为 $d=2^{p_1}+2^{p_2}+...+2^{p_i}$

所以直接 $log_2{d}$ 可以得到向上走的指数 $p$

而log函数需要预处理

for(int i = 1; i <= maxn; i++)//log2(i)+1
    {
        if((1 << lg[i - 1]) == i)
            lg[i] = lg[i - 1] + 1;
        else
            lg[i] = lg[i - 1];
    }

到相同高度后就可以开始查询LCA了

for(int i = lg[h[x]] - 1; i >= 0; i--)
    {
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    }

大体思路就是

从u和v最远的祖先开始

如果u的第2^i祖先等于 v的第2^i祖先，就不移动

否则u和v同时上移2^i个深度

最后u的父亲一定是u和v的LCA

#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn = 4e4 + 10;
int n, m;
int tot;
struct node
{
    int to;
    int next;
    int w;
};
node edges[maxn << 1];
int head[maxn];
int lg[maxn];
int h[maxn];
int d[maxn];//当前结点到根结点的深度
int f[maxn][30];//f[i][j] 表示 i 节点的 2^j 级祖先
void add_edges(int u, int v, int w)
{
    edges[++tot].to = v;
    edges[tot].next = head[u];
    edges[tot].w = w;
    head[u] = tot;
}
void dfs(int x, int fa)
{
    h[x] = h[fa] + 1;
    f[x][0] = fa;
    for(int i = 1; (1 << i) <= h[x]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x]; i; i = edges[i].next)
    {
        if(edges[i].to != fa)
        {
            d[edges[i].to] = d[x] + edges[i].w;
            dfs(edges[i].to, x);
        }
    }
}
int lca(int x, int y)
{
    if(h[x] < h[y])
        swap(x, y);
    while(h[x] > h[y])
        x = f[x][lg[h[x] - h[y]] - 1];
    if(x == y)
        return x;
    for(int i = lg[h[x]] - 1; i >= 0; i--)
    {
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= maxn; i++)//log2(i)+1
    {
        if((1 << lg[i - 1]) == i)
            lg[i] = lg[i - 1] + 1;
        else
            lg[i] = lg[i - 1];
    }
    while(T--)
    {
        tot = 0;
        memset(head, 0, sizeof(head));
        scanf("%d%d", &n, &m);
        int i, j, k;
        for(int t = 1; t < n; t++)
        {
            scanf("%d%d%d", &i, &j, &k);
            add_edges(i, j, k);
            add_edges(j, i, k);
        }
        dfs(1, -1);
        for(int t = 1; t <= m; t++)
        {
            scanf("%d%d", &i, &j);
            cout << d[i] + d[j] - 2 * d[lca(i, j)] << endl;
        }
    }
}