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;

        }

    }

}

巴特西

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

最新文章

热门文章