浅谈倍增法求解LCA

Luogu P3379 最近公共祖先

原题展现

题目描述

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

输入格式

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

接下来 N−1N−1 行每行包含两个正整数 x,yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 MM 行每行包含两个正整数 a,ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。

输出格式

输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。

样例输入 #1

复制代码
1
2
3
4
5
6
7
8
9
10
er-hljs
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

复制代码
1
2
3
4
5
er-hljs
4
4
1
4
4

提示

对于 30%30% 的数据，N≤10N≤10，M≤10M≤10。

对于 70%70% 的数据，N≤10000N≤10000，M≤10000M≤10000。

对于 100%100% 的数据，N≤500000N≤500000，M≤500000M≤500000。

样例说明：

该树结构如下：

第一次询问：2,42,4 的最近公共祖先，故为 44。

第二次询问：3,23,2 的最近公共祖先，故为 44。

第三次询问：3,53,5 的最近公共祖先，故为 11。

第四次询问：1,21,2 的最近公共祖先，故为 44。

第五次询问：4,54,5 的最近公共祖先，故为 44。

故输出依次为 4,4,1,4,44,4,1,4,4。

解析

本题是 LCA 的模板

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

暴力跳

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

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

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

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

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

倍增法

考虑一次跳多一点

记fau,kfau,k表示距离uu的边数为2k2k的祖先节点则fau,k=fafau,k−1,k−1fau,k=fafau,k−1,k−1可以通过dfs求出fafa

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

考虑求两点深度差，将差二进制拆分，每次跳一个22的幂，时间复杂度O(logn)O(logn)

当然，没必要真的二进制拆分，因为我们要知道是22的几次幂，所以用cmath的log2更加方便

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

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

一个性质：如果两点跳到LCA了，继续向上跳依然相等（易证）

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

于是想到一个办法：尝试枚举ii从3131到00,表示尝试跳2i2i

如果向上跳不相同的话，就向上跳，这样，枚举完，LCA就是fax,0fax,0

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cpp
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);
        }
    }
}

然后是求解

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cpp
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(logn)O(logn)算法

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

原题展现

题目描述

A 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。

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

输入格式

第一行有两个用一个空格隔开的整数 n,mn,m，表示 AA 国有 nn 座城市和 mm 条道路。

接下来 mm 行每行三个整数 x,y,zx,y,z，每两个整数之间用一个空格隔开，表示从 xx 号城市到 yy 号城市有一条限重为 zz 的道路。
注意： x≠yx≠y，两座城市之间可能有多条道路 。

接下来一行有一个整数 qq，表示有 qq 辆货车需要运货。

接下来 qq 行，每行两个整数 x,yx,y，之间用一个空格隔开，表示一辆货车需要从 xx 城市运输货物到 yy 城市，保证 x≠yx≠y

输出格式

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

样例输入 #1

复制代码
1
2
3
4
5
6
7
8
er-hljs
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 #1

复制代码
1
2
3
er-hljs
3
-1
3

提示

对于 30%30% 的数据，1≤n<10001≤n<1000，1≤m<10,0001≤m<10,000，1≤q<10001≤q<1000；

对于 60%60% 的数据，1≤n<10001≤n<1000，1≤m<5×1041≤m<5×104，1≤q<10001≤q<1000；

对于 100%100% 的数据，1≤n<1041≤n<104，1≤m<5×1041≤m<5×104，1≤q<3×1041≤q<3×104，0≤z≤1050≤z≤105。

解析

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

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

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

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

核心代码如下（码风十分奇怪）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
cpp
#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了前四道题，准备暴切第五题，看着这个题面，突然发现不太对....

他一看五道题的名字

XorCounttheNumberofDanceSchemesRelaxingTimeAnEasyProblemKilltheDuckXCRAK

XorCounttheNumberofDanceSchemesRelaxingTimeAnEasyProblemKilltheDuckXCRAK

XCR十分生气，想要杀了DengDuck

DengDuck跑到了一个有nn个结点，n−1n−1条边的树上

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

XCR现在有mm次询问，第i(1≤i≤m)i(1≤i≤m)次给出两个正整数xixi和yiyi,含义如下

DengDuck 在点 xi(1≤xi≤n)xi(1≤xi≤n) 上,XCR在点 yi(1≤yi≤n)yi(1≤yi≤n) 上

对于每次询问，请问XCR离DengDuck的距离是多少？

输入格式

第一行一个整数nn

接下来n−1n−1行每行三个正整数分别表示一条边的起点，终点，边权

第n+1n+1行一个正整数mm

接下来mm行每行两个正整数xixi和yiyi

输出格式

有mm行，每行一个正整数，表示DengDuck和XCR的距离

样例输入 #1

复制代码
1
2
3
4
5
6
7
input1
3
1 2 3
2 3 4
2

1 2
1 3

样例输出 #1

复制代码
1
2
output1
3
7

样例输入 #2

复制代码
1
2
3
4
5
6
7
8
9
input2
3
1 3 10
1 2 13
5
1 1
2 2
3 1
2 1
1 3

样例输出 #2

复制代码
1
2
3
4
5
output2
0
0
10
13
10

样例输入 #3

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
input3
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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
output3
50
0
40
61
32
48
0
79
89
57
46
63
11
30
46
79
38

提示

对于一定的数据	n,mn,m的范围	特殊限制
前5%5%的数据	1～20	无
前20%的数据	1～3000	无
另外的5%的数据	1～3000	m=1
所有数据	1～100000	无

解析

预处理出disi表示点i到根1的距离，答案是disx+disy−2dislca(x,y)

非常容易证明

代码如下

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
cpp
#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;
    }
}