Chenfan Blog

Do cool things that matter.

0%

理一个 LCA 模版

Posted on Edited on In

工作累了头昏脑涨，刷个题冷静一下。

顺手来理一下 LCA 的板子。

Tarjan 离线 LCA

前面在 【Tarjan 大佬的算法们】 中提到过他的离线 LCA 算法，就从这里开始。

原始算法具体见前文吧，还引用了别人的一个链接，里面有个动画演示的挺清楚的。

离线 LCA 的关键在于 dfs 遍历整个树的过程中，对于被询问的点对 (v, w)，要求其中一个点要先被访问过，然后再遍历到另一个点则可以通过查询前一个点所属的并查集来找到它们的 LCA，例如 v 先被访问，接下来遍历到 w，则它们的 LCA 是 getfather(v)，反正若 w 先被访问，接下来遍历到 v，则它们的 LCA 是 getfather(w)。查询结束再将 v 和 w 合并到同一个集合中（向树上父节点的方向合并）。

Tarjan 论文中的原始算法的树节点应该是保证有序的，然后通过先处理每一对 (vi, wi)，使得 vi < wi 来保证每次访问到 wi 时，它对应的 vi 都被访问过。

在通用的树中就只能在每一层 dfs 中询问跟当前层搜的父节点相关的边来查找这种对应关系了。

记两道模版题：

HDU 2586

【题意】

给出一棵树，询问树上的两个点，要求回答两个点之间的最近距离。

【分析】

树首先是任意给的，假定我们建出来的树根是 R，则对于一次询问的点对 (a, b)，可以在这棵树上找到它们的 LCA，记为 c。则 a 和 b 之间的距离就是：

$$Dis(R, a) - Dis(R, c) + Dis(R, b) - Dis(R, c) = Dis(R, a) + Dis(R, b) - 2*Dis(R, c)$$

在找 LCA 的 dfs 过程中顺手把每个节点到根节点的距离记出来即可。

HDU 2874

【题意】

跟前面类似，加了个条件是可能有多棵树。

【分析】

每对点对是否在同一棵树上可以在读取数据的时候直接用并查集判断联通性记下来，之后对所有未访问过的点做 Tarjan 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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: hdu2874
************************************************ */

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int father[10010];

int getfather(int x)
{
    if (father[x] != x) father[x] = getfather(father[x]);
    return father[x];
}

void link(int x, int y)
{
    father[getfather(x)] = getfather(y);
}

typedef struct nod
{
    int a, b, c;
} node;

bool op(node a, node b)
{
    if (a.a == b.a) return a.b < b.b;
    else return a.a < b.a;
}

node edge[20010];
int start[10010], num[10010], dist[10010];
bool flag[10010];

node q[2000010];
int qstart[10010], qnum[10010];
int res[1000010];

void tarjan(int now)
{
    father[now] = now;
    flag[now] = true;
    
    for (int i=0;i<num[now];i++)
    {
        int next = edge[start[now]+i].b;
        if (!flag[next])
        {
            dist[next] = dist[now]+edge[start[now]+i].c;
            tarjan(next);
            link(next, now);
        }
    }
    for (int i=0;i<qnum[now];i++)
    {
        int next = q[qstart[now]+i].b;
        if (res[q[qstart[now]+i].c] != -1 && flag[next])
        {
            int lca = getfather(next);
            res[q[qstart[now]+i].c] = dist[now]+dist[next]-2*dist[lca];
        }
    }
}

int main()
{
    freopen("in.txt", "r", stdin);

    int n, m, c;
    while (scanf("%d %d %d", &n, &m, &c) != EOF)
    {
        for (int i=1;i<=n;i++) father[i] = i;
        for (int i=0;i<m;i++)
        {
            int index = i << 1;
            scanf("%d %d %d", &edge[index].a, &edge[index].b, &edge[index].c);
            edge[index+1].b = edge[index].a;
            edge[index+1].a = edge[index].b;
            edge[index+1].c = edge[index].c;
            link(edge[index].a, edge[index].b);
        }
        memset(start, 0, sizeof(start));
        memset(num, 0, sizeof(num));
        m = m << 1;
        sort(&edge[0], &edge[m], op);
        for (int i=0,o=-1;i<m;i++)
        {
            if (o!=edge[i].a)
            {
                o = edge[i].a;
                start[o] = i;
            }
            num[o]++;
        }

        memset(res, 0, sizeof(res));
        for (int i=0;i<c;i++)
        {
            int index = i << 1;
            scanf("%d %d", &q[index].a, &q[index].b);
            q[index+1].a = q[index].b;
            q[index+1].b = q[index].a;
            q[index].c = i;
            q[index+1].c = i;
            if (getfather(q[index].a) != getfather(q[index].b)) res[i] = -1;
        }
        memset(qstart, 0, sizeof(qstart));
        memset(qnum, 0, sizeof(qnum));
        c = c << 1;
        sort(&q[0], &q[c], op);
        for (int i=0,o=-1;i<c;i++)
        {
            if (o != q[i].a)
            {
                o = q[i].a;
                qstart[o] = i;
            }
            qnum[o]++;
        }

        memset(flag, 0, sizeof(flag));
        memset(dist, 0, sizeof(dist));
        for (int i=1;i<=n;i++)
        if (!flag[i]) tarjan(i);

        c = c >> 1;
        for (int i=0;i<c;i++)
        {
            if (res[i] == -1) printf("Not connected\n");
            else printf("%d\n", res[i]);
        }

    }
    
    return 0;
}

dfs 过程中是先询问边还是先进行下一层的 dfs 不影响结果。

话说虽然前向星写习惯了，不过看人家写的数组邻接链表也挺好看的。

动态树（LCT）

前面 【HDU 3966】 用过一次 LCT 和树链剖分来维护树上一条路径上的点值，翻回去看的时候……妈呀，以前题解怎么都没好好写，自己都看不懂了，顺便拿到这里重新理一下思路。

LCT 的核心思路是用 splay 森林来维护 Preferred Path，核心操作是调整 Preferred Path 的 Access 操作，对于 LCT 来说，找 a、b 两点的 LCA 只需要两步：

  1. 首先 Access(a) ，此时 a 所在的 splay 树即为从根节点到 a 点所构成的 Preferred Path；
  2. 之后 Access(b)，找到从根节点到 b 点所构成的 Preferred Path 之后，此时 Splay 的根即为 a 和 b 的 LCA。

当然也有可能两次 Access 操作之后的 Preferred Path 的根不是同一个，那就意味着这两个点是分属于两棵不同的树，不存在 LCA，特判一下就好了。

所以上面那题的 LCT 模版是：

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: HDU2874-LCT
************************************************ */

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct nod
{
    int a, b, c;
} node;

bool op(node a, node b)
{
    if (a.a == b.a) return a.b < b.b;
    else return a.a < b.a;
}

node edge[20010];
int start[10010], num[10010], dist[10010];

int sons[10010][2];
int father[10010];
bool root[10010];

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    root[s] = true;
    while (!q.empty())
    {
        int now = q.front();
        for (int i=0;i<num[now];i++)
        if (!root[edge[start[now]+i].b])
        {
            father[edge[start[now]+i].b] = now;
            dist[edge[start[now]+i].b] = dist[now] + edge[start[now]+i].c;
            root[edge[start[now]+i].b] = true;
            q.push(edge[start[now]+i].b);
        }
        q.pop();
    }
}

void rotate(int x,int w) //rotate(node,0/1)
{
    int y=father[x];

    sons[y][!w]=sons[x][w];
    if (sons[x][w]) father[sons[x][w]]=y;
    father[x]=father[y];
    if (father[y]&&(!root[y])) sons[father[y]][y==sons[father[y]][1]]=x;
    sons[x][w]=y;
    father[y]=x;

    if (root[y])
    {
        root[x]=true;
        root[y]=false;
    }
}

void splay(int x) //splay(node)
{
    while(!root[x])
    {
        if (root[father[x]]) rotate(x,x==sons[father[x]][0]);
        else 
        {
            int t=father[x];
            int w=(sons[father[t]][0]==t);
            if (sons[t][w]==x)
            {
                rotate(x,!w);
                rotate(x,w);
            } else 
            {
                rotate(t,w);
                rotate(x,w);
            }
        }
    }
}

void access(int v)
{
    int u=v;
    v=0;
    while(u)
    {
        splay(u);
        root[sons[u][1]]=true;
        sons[u][1]=v;
        root[v]=false;
        v=u;
        u=father[u];
    }
}

int check(int x, int y)
{
    access(x);
    int root_x = x;
    while (father[root_x]) root_x = father[root_x];
    while (sons[root_x][0]) root_x = sons[root_x][0];

    int u = y, v = 0;
    while(u)
    {
        splay(u);
        root[sons[u][1]] = true;
        sons[u][1] = v;
        root[v] = false;
        v = u;
        u = father[u];
    }
    int root_y = v;
    while (sons[root_y][0]) root_y = sons[root_y][0];
    if (root_x != root_y) return -1;
    else return dist[x] + dist[y] - 2*dist[v];
}

int main()
{
    freopen("in.txt", "r", stdin);

    int n, m, c;
    while (scanf("%d %d %d", &n, &m, &c) != EOF)
    {
        for (int i=0;i<m;i++)
        {
            int index = i << 1;
            scanf("%d %d %d", &edge[index].a, &edge[index].b, &edge[index].c);
            edge[index+1].b = edge[index].a;
            edge[index+1].a = edge[index].b;
            edge[index+1].c = edge[index].c;
        }
        memset(start, 0, sizeof(start));
        memset(num, 0, sizeof(num));
        m = m << 1;
        sort(&edge[0], &edge[m], op);
        for (int i=0,o=-1;i<m;i++)
        {
            if (o!=edge[i].a)
            {
                o = edge[i].a;
                start[o] = i;
            }
            num[o]++;
        }
        memset(root, 0, sizeof(root));
        memset(dist, 0, sizeof(dist));
        memset(father, 0, sizeof(father));
        memset(sons, 0, sizeof(sons));
        for (int i=1;i<=n;i++)
        if (!root[i]) bfs(i);

        for (int i=0;i<c;i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            int res = check(x, y);
            if (res == -1) printf("Not connected\n");
            else printf("%d\n", res);
        }
    }
    
    return 0;
}

从最后的求解过程上来看，应该比离线的要更顺一点，毕竟在线算法不用多考虑记录输出顺序什么的。

树链剖分

还是看前面 【HDU 3966】 的时候……发现树链剖分忘得差不多了，顺手再补一个树剖找 LCA 的模版吧。

树链剖分的原理是把整棵树按照一条一条树边组成的链划开，每条链相当于一个区间，那对树上的某条路径的操作就成了对树上的一条或者多条树链的操作了，具体维护区间的部分可以用树状数组啊、线段树啊什么的来做。

划分树链的基本思路是对整棵树进行轻重边划分，定义 size(x) 是以 x 为根的子树的节点个数，这里的重边就是 x 和它节点数更多的一个子节点（size 更大的一个子节点）组成的边。

这里会有两个性质：

  1. 若 (father, son) 是一条轻边，则 size(son) <= size(father)/2
  2. 从树根到某一个点的路径上的轻边的个数不会超过 O(logn)

划分好轻重边之后，从根节点开始把所有连着的重边连起来，就成了一条重链，重链就是前面说的需要从树上剖出来的树链啦。

这个过程可以用一次 bfs 加两次队列遍历来完成：

  1. 首先 bfs 构图，把所有节点的父节点 father 和距离根节点的层数 level 标记好；
  2. 根据前面 bfs 过程中记录下来的队列顺序，反向遍历一遍，自底向上维护好每个节点的 size，标记重边也是在这里完成；
  3. 根据前面 bfs 过程中记录下来的队列顺序，正向遍历一遍，自顶向下对每条重边进行剖分，大概是一个切下来一条链放好，再切下一条链放好这样的过程。

那么 LCA 要怎么找呢？

在树链结构上找 a、b 两点的 LCA 即走完各自所在的树链，沿着它的轻边向上找，直到找到各自路径上的两个点在同一条树链上，那么深度较浅的那个点就是 a、b 两点的 LCA 了。

由于从树根到某一个点的路径上的轻边的个数不会超过 O(logn) 这个性质，每次找 LCA 的复杂度是 O(logn)。

模版如下：

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: HDU2874-TreeCut
************************************************ */

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct nod
{
    int a, b, c;
} node;

bool op(node a, node b)
{
    if (a.a == b.a) return a.b < b.b;
    else return a.a < b.a;
}

node edge[20010];
int start[10010], num[10010], dist[10010];

int son[10010], father[10010], level[10010], size[10010], top[10010], pos[10010];

int q[10010];
void bfs(int n)
{
    int head = 0, tail = 0;
    memset(level, 0, sizeof(level));
    memset(father, 0, sizeof(father));
    memset(dist, 0, sizeof(dist));
    memset(son, 0, sizeof(son));

    for (int x=1;x<=n;x++)
    if (!level[x])
    {
        q[head] = x;
        level[x] = 1;
        tail = head;
        while (head <= tail)
        {
            int now = q[head];
            size[now] = 1;
            for (int i=0;i<num[now];i++)
            {
                int next = edge[start[now]+i].b;
                if (next != father[now])
                {
                    father[next] = now;
                    dist[next] = dist[now]+edge[start[now]+i].c;
                    level[next] = level[now]+1;
                    tail++;
                    q[tail] = next;
                }
            }
            head ++;
        }
    }
    for (int i=n-1;i>=0;i--)
    {
        int now = q[i];
        if (father[now])
        {
            size[father[now]]+=size[now];
            if (son[father[now]]==0 || size[now]>size[son[father[now]]])
            son[father[now]] = now;
        }
    }
    int tot = 1;
    for (int i=0;i<n;i++)
    {
        int now = q[i];
        if (son[father[now]] == now) top[now] = top[father[now]];
        else
        {
            top[now] = now;
            while (now)
            {
                pos[now] = tot++;
                now = son[now];
            }
        }
    }
}

int lca(int x, int y)
{
    while (top[x] != top[y])
    {
        if (level[top[x]] < level[top[y]]) swap(x, y);
        x = father[top[x]];
    }
    if (x==0 && y==0) return -1;
    if (level[x] > level[y]) swap(x, y);
    return x;
}

int main()
{
    freopen("in.txt", "r", stdin);

    int n, m, c;
    while (scanf("%d %d %d", &n, &m, &c) != EOF)
    {
        for (int i=0;i<m;i++)
        {
            int index = i << 1;
            scanf("%d %d %d", &edge[index].a, &edge[index].b, &edge[index].c);
            edge[index+1].b = edge[index].a;
            edge[index+1].a = edge[index].b;
            edge[index+1].c = edge[index].c;
        }
        memset(start, 0, sizeof(start));
        memset(num, 0, sizeof(num));
        m = m << 1;
        sort(&edge[0], &edge[m], op);
        for (int i=0,o=-1;i<m;i++)
        {
            if (o!=edge[i].a)
            {
                o = edge[i].a;
                start[o] = i;
            }
            num[o]++;
        }
        bfs(n);

        for (int i=0;i<c;i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            int res = lca(x, y);
            if (res == -1) printf("Not connected\n");
            else printf("%d\n", dist[x] + dist[y] - 2*dist[res]);
        }
    }
    
    return 0;
}

话说从 HDU 提交的结果上来看，树链剖分是最快的，LCT 次之，Tarjan 离线最慢。

Related Posts