浅谈倍增法求解LCA

Luogu P3379 最近公共祖先

原题展现

题目描述

如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 \(N,M,S\),分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 \(N-1\) 行每行包含两个正整数 \(x, y\),表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边(数据保证可以构成树)。

接下来 \(M\) 行每行包含两个正整数 \(a, b\),表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。

输出格式

输出包含 \(M\) 行,每行包含一个正整数,依次为每一个询问的结果。

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

对于 \(30\%\) 的数据,\(N\leq 10\)\(M\leq 10\)

对于 \(70\%\) 的数据,\(N\leq 10000\)\(M\leq 10000\)

对于 \(100\%\) 的数据,\(N\leq 500000\)\(M\leq 500000\)

样例说明:

该树结构如下:

《浅谈倍增法求解LCA》

第一次询问:\(2, 4\) 的最近公共祖先,故为 \(4\)

第二次询问:\(3, 2\) 的最近公共祖先,故为 \(4\)

第三次询问:\(3, 5\) 的最近公共祖先,故为 \(1\)

第四次询问:\(1, 2\) 的最近公共祖先,故为 \(4\)

第五次询问:\(4, 5\) 的最近公共祖先,故为 \(4\)

故输出依次为 \(4, 4, 1, 4, 4\)

解析

本题是 LCA 的模板

LCA 的做法很多,比如暴力跳,倍增

暴力跳

让深度大的一点不断向上跳,直到两点深度相等

如果两点深度相同但是并不相等,可以两点一起跳

在随机数据下表现优异,因为树会比较平衡,所以近似\(O(\log n)\)

通常会被卡成单次\(O(n)\),其实不难构造,可以构造一个深度大的树(比如链)

本人出的一道题思想类似这样,不过这道题保证了平衡

倍增法

考虑一次跳多一点

\(fa_{u,k}\)表示距离\(u\)的边数为\(2^k\)的祖先节点则\(fa_{u,k}=fa_{fa_{u,k-1},k-1}\)可以通过dfs求出\(fa\)

如果求LCA,我们可以很快让两点来到相同的深度

考虑求两点深度差,将差二进制拆分,每次跳一个\(2\)的幂,时间复杂度\(O(\log n)\)

当然,没必要真的二进制拆分,因为我们要知道是\(2\)的几次幂,所以用cmathlog2更加方便

这里有一个优化:用\(O(n)\)的时间复杂度递推求出log2的值

然后,如果两点深度相同不相等,有一个自认为巧妙的方法求解

一个性质:如果两点跳到LCA了,继续向上跳依然相等(易证)

如果两点向上跳不相等,那么一定可以继续跳

于是想到一个办法:尝试枚举\(i\)\(31\)\(0\),表示尝试跳\(2^i\)

如果向上跳不相同的话,就向上跳,这样,枚举完,LCA就是\(fa_{x,0}\)

核心代码如下,首先是预处理

void dfs(long long x,long long fa)
{
    f[x][0]=fa;
    dep[x]=dep[fa]+1;
    for(int i=1;i<=31;i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=h[x];i;i=a[i].next)
    {
        if(a[i].to!=fa)
        {
            dfs(a[i].to,x);
        }
    }
}

然后是求解

if(dep[x]<dep[y])
{
    swap(x,y);
}   
while(dep[x] > dep[y])
{
    x = f[x][lg[dep[x]-dep[y]] - 1];
}
if(x==y)
{
    cout<<x<<endl;
    continue;
}
for(int k = lg[dep[x]] - 1; k >= 0;k--) 
{
    if(f[x][k] != f[y][k]) 
    {
        x = f[x][k], y = f[y][k];
    }
}

于是,我们得到了一个严格的\(O(\log n)\)算法

Luogu P1967 [NOIP2013 提高组] 货车运输

原题展现

题目描述

A 国有 \(n\) 座城市,编号从 \(1\)\(n\),城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制,简称限重。

现在有 \(q\) 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$,表示 \(A\) 国有 $ n$ 座城市和 \(m\) 条道路。

接下来 \(m\) 行每行三个整数 \(x, y, z\),每两个整数之间用一个空格隔开,表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 \(z\) 的道路。
注意: \(x \neq y\),两座城市之间可能有多条道路 。

接下来一行有一个整数 \(q\),表示有 \(q\) 辆货车需要运货。

接下来 \(q\) 行,每行两个整数 \(x,y\),之间用一个空格隔开,表示一辆货车需要从 \(x\) 城市运输货物到 \(y\) 城市,保证 \(x \neq y\)

输出格式

共有 \(q\) 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。
如果货车不能到达目的地,输出 \(-1\)

样例输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 #1

3
-1
3

提示

对于 \(30\%\) 的数据,\(1 \le n < 1000\)\(1 \le m < 10,000\)\(1\le q< 1000\)

对于 \(60\%\) 的数据,\(1 \le n < 1000\)\(1 \le m < 5\times 10^4\)\(1 \le q< 1000\)

对于 \(100\%\) 的数据,\(1 \le n < 10^4\)\(1 \le m < 5\times 10^4\),$1 \le q< 3\times 10^4 $,\(0 \le z \le 10^5\)

解析

因为我们想要经过的最小边最大,那么不妨构造一个最大生成树(建议使用克鲁斯卡尔算 法),这样每条边都能尽可能大

然后问题转换为树上查询,同样利用倍增法求\(x->LCA,y->LCA\)路径中的最小边,也是可以预处理的

不过问题不保证树联通,需要判断是否有解

克鲁斯卡尔的优势就体现出来了,我们已经处理了并查集,如果两点祖先不同就直接判断为无解

核心代码如下(码风十分奇怪)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct road
{
    ll s,t,w;
}r[200005];
struct node
{
    ll to,next,w;
}a[200005];
ll n,m,t,k,x,y,fa2[100005],h[100005],fa[100005][33],f[100005][33],dep[100005],lg[100005];
bool cmp(road x,road y)
{
    return x.w>y.w;
}
void add(int x,int y,int z)
{
    t++;
    a[t].to=y;
    a[t].w=z;
    a[t].next=h[x];
    h[x]=t;
}
int find(int x)
{
    if(fa2[x]==x)return x;
    return fa2[x]=find(fa2[x]);
}
void dfs(long long x,long long fn)
{
    fa[x][0]=fn;
    dep[x]=dep[fn]+1; 
    for(int i=1;i<=31;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        f[x][i]=min(f[x][i-1],f[fa[x][i-1]][i-1]);//f数组表示x到fa[x][i]路径的最小值
    }
    for(int i=h[x];i;i=a[i].next)
    {
        if(a[i].to!=fn)
        {   
            f[a[i].to][0]=a[i].w;
            dfs(a[i].to,x);
        }
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }   
    while(dep[x] > dep[y])
    {
        x = fa[x][lg[dep[x]-dep[y]] - 1];
    }
    if(x==y)
    {
        return x;
    }
    for(int k = lg[dep[x]] - 1; k >= 0;k--) 
    {
        if(fa[x][k] != fa[y][k]) 
        {
            x = fa[x][k], y = fa[y][k];
        }
    }    
    return fa[x][0];
}
int work(int x,int y)//求解x到y路径的最小值,保证y是x祖先
{
    ll ans=1e9,deph=dep[x]-dep[y];
    while(deph!=0)
    {
        ll t=lg[deph]-1;
        ans=min(ans,f[x][t]);
        x=fa[x][t];
        deph=dep[x]-dep[y];
    }
    return ans;
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa2[i]=i;
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>r[i].s>>r[i].t>>r[i].w;
    }
    sort(r+1,r+m+1,cmp);//克鲁斯卡尔
    int k=n-1;
    for(int i=1;i<=m;i++)
    {
        if(k==0)break;
        if(find(r[i].s)!=find(r[i].t))
        {
            add(r[i].s,r[i].t,r[i].w);
            add(r[i].t,r[i].s,r[i].w);
            fa2[find(r[i].s)]=find(r[i].t);
            k--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(find(i)==i)
        {
            dfs(i,0);
        }
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>x>>y;
        if(find(x)!=find(y))
        {
            cout<<-1<<endl;
            continue;
        }
        int lcah=lca(x,y);
        cout<<min(work(x,lcah),work(y,lcah))<<endl;
    }
}

Duck006[DuckOI]Kill the Duck

原题展现

温馨提示

Duck非常不要脸,单推自己的题

后来发现其实有好多一样的题

  • 贪玩的小孩
  • HDU 2586 How far away?

题目描述

XCR是世界名列前茅的OIer,今天在打模拟赛。

他已经AC了前四道题,准备暴切第五题,看着这个题面,突然发现不太对….

他一看五道题的名字

\[\mathtt{\color{red}{X}\color{black}{or}}\\ \mathtt{\color{red}{C}\color{black}{ount\;the\;Number\;of\;Dance\;Schemes}}\\ \mathtt{\color{red}{R}\color{black}{elaxing\;Time }}\\ \mathtt{\color{red}{A}\color{black}{n\; Easy\;Problem}}\\ \mathtt{\color{red}{K}\color{black}{ill\;the\;Duck}}\\ \mathtt{\huge{\color{red}{XCRAK}}} \]

XCR十分生气,想要杀了DengDuck

DengDuck跑到了一个有\(n\)个结点,\(n-1\)条边的树上

这个树的每个边都是无向的,都有边权

XCR现在有\(m\)次询问,第\(i(1 \leq i \leq m)\)次给出两个正整数\(x_i\)\(y_i\),含义如下

DengDuck 在点 \(x_i(1 \leq x_i \leq n)\) 上,XCR在点 \(y_i(1 \leq y_i \leq n)\)

对于每次询问,请问XCR离DengDuck的距离是多少?

输入格式

第一行一个整数\(n\)

接下来\(n-1\)行每行三个正整数分别表示一条边的起点,终点,边权

\(n+1\)行一个正整数\(m\)

接下来\(m\)行每行两个正整数\(x_i\)\(y_i\)

输出格式

\(m\)行,每行一个正整数,表示DengDuck和XCR的距离

样例输入 #1

3
1 2 3
2 3 4
2

1 2
1 3

样例输出 #1

3
7

样例输入 #2

3
1 3 10
1 2 13
5
1 1
2 2
3 1
2 1
1 3

样例输出 #2

0
0
10
13
10

样例输入 #3

14
5 7 12
7 11 15
5 14 12
14 3 17
7 1 19
14 4 14
1 12 16
1 6 16
12 9 19
9 10 10
7 2 11
4 8 10
2 13 14
17
6 11
14 14
13 11
6 10
12 6
8 7
9 9
10 11
13 10
1 4
2 12
13 4
2 7
2 1
12 2
10 11
4 7

样例输出 #3

50
0
40
61
32
48
0
79
89
57
46
63
11
30
46
79
38

提示

对于一定的数据\(n,m\)的范围特殊限制
\(5\%\)的数据\(1~20\)
\(20\%\)的数据\(1~3000\)
另外的\(5\%\)的数据\(1~3000\)\(m=1\)
所有数据\(1~100000\)

解析

预处理出\(dis_i\)表示点\(i\)到根\(1\)的距离,答案是\(dis_x+dis_y-2dis_{lca(x,y)}\)

非常容易证明

代码如下

#include <bits/stdc++.h>
using namespace std;
int n, k, b[1000005], x, y, z, tot, h[500005], len[500005], fa[500005][33], dep[500005], lg[500005],
    f[1000005], ans;
struct node {
    int to, next, w;
} a[1000005];
void dfs(long long x, long long fn, long long l) {
    fa[x][0] = fn;
    dep[x] = dep[fn] + 1;
    len[x] = l;
    for (int i = 1; i <= 31; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (int i = h[x]; i; i = a[i].next) {
        if (a[i].to != fn) {
            dfs(a[i].to, x, l + a[i].w);
        }
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    while (dep[x] > dep[y]) {
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    }
    if (x == y) {
        return x;
    }
    for (int k = lg[dep[x]] - 1; k >= 0; k--) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k], y = fa[y][k];
        }
    }
    return fa[x][0];
}
void add(int x, int y, int z) {
    ++tot;
    a[tot].to = y;
    a[tot].next = h[x];
    a[tot].w = z;
    h[x] = tot;
}
void answer(int x, int fn) {
    for (int i = h[x]; i; i = a[i].next) {
        if (a[i].to != fn) {
            answer(a[i].to, x);
            f[x] += f[a[i].to];
        }
    }
    ans = max(ans, f[x]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    }
    for (int i = 1; i <= n - 1; i++) {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    dfs(1, 0, 0);
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> x >> y;
        int t = lca(x, y);
        cout << len[x] + len[y] - 2 * len[t] << endl;
    }
}
    原文作者:DengDuck
    原文地址: https://www.cnblogs.com/I-am-joker/p/16361172.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞