算法图算法

问题规约的艺术：无向基环树的直径

字数统计: 4k字   |   阅读时长: 18分
,

摘要: 基环树的概念与例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于无向图，N 个点的树有 N - 1 条边，在树上任意加一条边，会形成一个环，除了环之外，其余部分由若干子树构成。

这种 N 个点 N 条边的连通无向图称为基环树。若干基环树组成的森林，为基环树森林。

有向图也有类似概念，N 个点，N 条边:

  • 每个节点有且仅有一条入边的有向图，称为外向树。看起来
  • 每个节点有且仅有一条出边的有向图，称为内向树。

基环树结构在图论中也算比较简单的结构，但是比树还是复杂一些。经常作为树模型的扩展：例如基环树的直径，基环树的两点间距离，基环树DP等。

办法一般是先找出图中唯一的环，再把环作为基环树的广义根节点，除了环以外的部分按照若干棵树来处理，最后再考虑与环一起计算。

本文我们解决基环树的直径问题，这个问题整体上非常复杂，但是通过拆解，可以将它们规约成几个小问题，这些小问题都是之前已经解决的问题，包括：

  • 在无向图中寻找环的问题：解法是图的 DFS 遍历
  • 树的直径问题：解法是树形 DP
  • 环形的处理：解法是复制后连接成两倍长度的线性序列
  • 滑动窗口最值问题：解法是单调队列
  • 区间求和问题：解法是前缀和

这几个问题我们之前都解决过，在解决了以上问题的基础上，下面我们来求基环树的直径。

岛屿游览 (基环树的直径)

你准备游览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。

同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。

相对于乘船而言，你更喜欢步行。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制：

  1. 可以自行挑选一个岛开始游览。
  2. 任何一个岛都不能游览一次以上。
  3. 无论任何时间你都可以由你现在所在的岛 S 去另一个你从未到过的岛 D。由 S 到 D 可以有以下方法：

（1）步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。

（2）渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D （当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第 1 行包含整数 N。
第 2..N+1 行，每行包含两个整数 a 和 L，第 i+1 行表示岛屿 i 上建了一座通向岛屿 a 的桥，桥的长度为  。

输出格式
输出一个整数，表示结果。
对某些测试，答案可能无法放进 32−bit 整数。

数据范围
2<=N<=1e6,
1<=L<=1e8

输入样例：
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
输出样例：
24

问题分析

建图与形态分析

首先看一下图的建立过程及其形态。

场景描述中说从每个岛屿出发向另外一座岛屿建了一座桥，也就是每个节点都刚好有一条出边，一共有 $N$ 个节点的话，共有 $N$ 条边。

但是没有说所有的岛屿是连通起来的，因此图的形态是一个森林，对于森林中的第 $i$ 棵树，如果有 $N_{i}$ 个节点，则有 $N_{i}$ 条边i，边上带有长度。

桥建好之后，双向都可以通行。因此给图中的 $N$ 个节点连好 $N$ 条边后，讲所有的边视为无向边。此时对于森林中的每一棵树，都是基环树的形态。

因此岛屿整体呈一个基环树森林的形态。

抽象与规约

根据两条行动规则。同一个基环树内只能走桥，只有在离开一个基环树到另一个基环树时，才可以坐船。

坐船离开某个基环树后，以后就不可以再回来了。因此在离开某个基环树之前，应该尽可能在该基环树内多走，最长可以走的长度为基环树的直径。因此可以走过的最大长度为所有基环树的直径的和。

下面的问题是如何求基环树的直径。

算法：基环树的直径

基环树的最长链有两种情况：

(1) 不经过环，在去掉环之后的某棵子树上。

(2) 经过环，两端分别在去掉环之后的某两棵子树上。

基环树中的环：DFS

在图上 DFS 遍历一轮，相当于遍历了整棵基环树。把环上的点做标记，共 $t$ 个节点 $s_{0}, s_{1}, \cdots, s_{t-1}$。

DFS 返回 $circle[0\cdots t-1]$, 以及 $dist[0\cdots t-1]$，其中：

  • $circle[i] = s_{i}$，表示第 $i$ 个节点的编号为 $s_{i}$。
  • $dist[i] = \epsilon(s_{i}, s_{i+1})$，表示环上的边 $s_{i}, s_{i+1}$ 的长度。

树的直径问题：树形DP

从每个 $s_{i}$ 出发，不经过环上其它节点，DFS 一轮，相当于遍历了以 $s_{i}$ 为根的子树。在该子树中，按照树的直径的算法，走一遍树形 DP 并更新答案，就处理了第 (1) 种情况。算法和代码模板参考文章 【树形DP】树的直径。同时，记录 $s_{i}$ 子树的最大深度，记为 $d[s_{i}]$，在处理第 (2) 种情况时有用。

环形问题：复制拼接变成2倍长度的线性问题

对于第 (2) 种情况，我们要找到环上的两个点 $s_{i}$, $s_{j}$，使得 $d[s_{i}] + d[s_{j}] + sums(s_{i}, s_{j})$ 最大。这是一个环形上的问题，可以通过复制一倍接在后面的做法解决，算法和代码参考文章 环形DP。

复制一倍后，原来的环变为线性序列 $s_{0}s_{1}\cdots s_{t-1}s_{t}s_{t+1}\cdots s_{2t-1}$，其中 $s_{i} = s_{t+i}, i=0,1,\cdots,t-1$。

对应地，$circle$ 和 $dist$ 也复制一倍。$circle[i] = circle[t+i]$、$dist[i] = dist[t+i]$。

滑动窗口最值问题：单调队列

下面我们看一下要最大化的式子。其中 $d[s_{i}] + d[s_{j}] = d[circle[i]] + d[circle[j]]$，这部分比较直接。下面我们看 $sums(s_{i}, s_{j})$，这部分表示路径 $s_{i} \rightarrow \cdots \rightarrow s_{j}$ 的长度，也就是 $\epsilon(s_{i}, s_{i+1}) + \epsilon(s_{i+1}, s_{i+2}) + \cdots + \epsilon(s_{j-1}, s_{j})$，结果为：

这部分可以用前缀和预处理：

1
2
3
4
5
sums[0] = 0
sums[1] = dist[0]
sums[2] = dist[0] + dist[1]
...
sums[i] = dist[0] + ... + dist[i - 1]

此后区间 $dist[i\cdots j]$ 的和为 $sums[j+1] - sums[i]$，于是有 $\sum\limits_{k=i}\limits^{j-1}dist[k] = sums[j] - sums[i]$。

于是我们要在加长后的线性序列上做的事情是：对于满足 $0 \leq i < j \leq 2t-1$ 且 $j - i + 1 \leq t$ 的 $(i, j)$，以下公式的最小值是多少：

对于给定的 $j$，$d[circle[j]] + sums[j]$ 是固定的，我们要找 $\max(0, j + 1 - t) \leq i < j$ 上 $d[circle[i]] - sums[i]$ 的最大值。

这是单调队列解决滑动窗口最值的标准问题，算法和代码参考文章 单调队列。

从 $1$ 到 $2t - 1$ 枚举 $j$，此时双端队列 $deq$ 中存放的是 $[max(0, j + 1 - t), j - 1]$ 范围的下标 $i$，并且从队尾到队头，$d[circle[i]] - sums[i]$ 单调递增。

此时用 $d[circle[deq.front()]] - sums[deq.front()]$ 来更新答案。然后将 $j$ 从队尾压入。在压入前，将所有小于等于 $d[circle[j]] - sums[j]$ 的下标从队尾弹出。

压入 $j$ 之后，此时的队头表示的下标 $i$ 可能就不满足花窗长度限制了，如果 $deq.front() < max(0, j + 2 - t)$，则弹出。

代码 (C++)

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
#include <iostream>
#include <cmath>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

struct Edge
{
    int v;
    int L;
    int id;
    Edge(){}
    Edge(int v, int L, int id):v(v),L(L),id(id){}
};

void dfs1(const vector<vector<Edge>>& g, const int u, vector<int>& visited, vector<int>& circle, vector<int>& dist, vector<Edge>& path)
{
    // 遍历基环树、记录环
    visited[u] = 1;
    for(const Edge& e: g[u])
    {
        int v = e.v;
        int l = path.size();
        int id = e.id;
        if(l > 0 && path[l - 1].id == id)
            continue;
        if(visited[v] == 2)
            continue;
        if(visited[v] == 1)
        {
            // 找到环，记录环
            circle.push_back(u);
            dist.push_back(path[l - 1].L);
            int i = l - 1;
            while(path[i].v != v)
            {
                circle.push_back(path[i].v);
                dist.push_back(path[i - 1].L);
                i--;
            }
            circle.push_back(v);
            dist.push_back(e.L);
            continue;
        }
        path.push_back(Edge(u, e.L, e.id));
        dfs1(g, v, visited, circle, dist, path);
        path.pop_back();
    }
    visited[u] = 2;
}

long long dfs2(const vector<vector<Edge>>& g, const int u, long long& ans, const int sl, const int sr, const int prev)
{
    // 树形 DP 求直径，在 ans 中更新，返回最大深度
    long long max1 = 0;
    long long max2 = 0;
    for(const Edge& e: g[u])
    {
        int v = e.v;
        if(v == sl || v == sr)
            continue;
        if(v == prev)
            continue;
        long long max_d = dfs2(g, v, ans, sl, sr, u);
        if(max_d + e.L > max1)
        {
            max2 = max1;
            max1 = max_d + e.L;
        }
        else if(max_d + e.L > max2)
            max2 = max_d + e.L;
        ans = max(ans, max1 + max2);
    }
    return max1;
}

long long solve(const vector<vector<Edge>>& g, const int N, const int s, vector<int>& visited, vector<long long>& d)
{
    vector<int> circle;
    vector<int> dist;
    vector<Edge> path;
    // 搜索环
    dfs1(g, s, visited, circle, dist, path);

    int t = circle.size();
    long long ans1 = 0; // 第一种情况
    for(int i = 0; i < t; ++i)
    {
        int si = circle[i];
        int sl = circle[(i + t - 1) % t];
        int sr = circle[(i + 1) % t];
        // 树的直径
        d[si] = dfs2(g, si, ans1, sl, sr, -1);
    }

    // circle[i..j]：d[circle[i]] + d[circle[j]] + dist[i, j] 的最大值
    // 枚举 j，找一个 max(0, j - t + 1) <= i <= j - 1，使得 d[circle[i]] + d[circle[j]] + sums[j] - sums[i] 最大
    circle.insert(circle.end(), circle.begin(), circle.end());
    dist.insert(dist.end(), dist.begin(), dist.end());
    vector<long long> sums(t * 2 + 1);
    for(int i = 1; i <= t * 2; ++i)
        sums[i] = sums[i - 1] + dist[i - 1];

    deque<int> deq;
    deq.push_back(0);
    long long ans2 = 0; // 第二种情况
    for(int j = 1; j < t * 2; ++j)
    {
        // deq 中是 [max(0, j - t + 1), j - 1]

        // 更新答案
        ans2 = max(ans2, d[circle[j]] + sums[j] + d[circle[deq.front()]] - sums[deq.front()]);

        // 插入 j 保持单调性
        while(!deq.empty() && d[circle[deq.back()]] - sums[deq.back()] <= d[circle[j]] - sums[j])
            deq.pop_back();
        deq.push_back(j);

        // 弹出 <=
        if(!deq.empty() && deq.front() < j - t + 2)
            deq.pop_front();
    }

    return max(ans1, ans2);
}

int main()
{
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    vector<vector<Edge>> g(N + 1);
    for(int i = 1; i <= N; ++i)
    {
        int a, L;
        cin >> a >> L;
        g[i].emplace_back(a, L, i);
        g[a].emplace_back(i, L, i);
    }

    long long ans = 0;
    vector<int> visited(N + 1);
    vector<long long> d(N + 1);
    for(int s = 1; s <= N; ++s)
    {
        if(visited[s] == 0)
        {
            ans += solve(g, N, s, visited, d);
        }
    }

    cout << ans << endl;
}

代码 (数组模拟链表，C++)

参考 用数组模拟链表的方式实现【带权有向图的邻接表】，本题的邻接表用 vector<vector<int>> 会被卡，把邻接表用数组模拟链表的方式实现，其余部分的实现不变，即可通过。

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;

const int E_SIZE = 2e6 + 5; // 总边数
const int V_SIZE = 2e6 + 5; // 总点数

int head[V_SIZE]; // head[i] 的值是 ver 下标，相当于链表节点指针
int ver[E_SIZE]; // 边的终点，相当于链表节点的 v 字段
int edge[E_SIZE]; // 边的权重，相当于链表节点的 w 字段
int edge_id[E_SIZE]; // 边的id
int next_[E_SIZE]; // 相当于链表节点的 next_ 字段

// tot 表示 node 数组(这里是 ver 和 next_)已使用的最右位置，而不是链表长度
int tot; // 可以表示边的 id

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(next_, -1, sizeof(head));
}

void add(int x, int y, int z, int id)
{
    // 增加有向边 (x, y), 权值为 z
    ver[++tot] = y;
    edge[tot] = z;
    next_[tot] = head[x];
    head[x] = tot; // 在表头 x 处插入
    edge_id[tot] = id;
}

struct Edge
{
    int v;
    int L;
    int id;
    Edge(){}
    Edge(int v, int L, int id):v(v),L(L),id(id){}
};

void dfs1(const int u, vector<int>& visited, vector<int>& circle, vector<int>& dist, vector<Edge>& path)
{
    // 遍历基环树、记录环
    visited[u] = 1;

    // 访问从 u 出发的所有边
    for(int i = head[u]; i != -1; i = next_[i])
    {
        // 找到有向边 (u, v) 其权值为 L，含边的 id
        int v = ver[i];
        int L = edge[i];
        int id = edge_id[i];
        int l = path.size();
        if(l > 0 && path[l - 1].id == id)
            continue;
        if(visited[v] == 2)
            continue;
        if(visited[v] == 1)
        {
            // 找到环，记录环
            circle.push_back(u);
            dist.push_back(path[l - 1].L);
            int i = l - 1;
            while(path[i].v != v)
            {
                circle.push_back(path[i].v);
                dist.push_back(path[i - 1].L);
                i--;
            }
            circle.push_back(v);
            dist.push_back(L);
            continue;
        }
        path.push_back(Edge(u, L, id));
        dfs1(v, visited, circle, dist, path);
        path.pop_back();
    }
    visited[u] = 2;
}

long long dfs2(const int u, long long& ans, const int sl, const int sr, const int prev)
{
    // 树形 DP 求直径，在 ans 中更新，返回最大深度
    long long max1 = 0;
    long long max2 = 0;

    for(int i = head[u]; i != -1; i = next_[i])
    {
        // 找到有向边 (u, v) 其权值为 L，含边的 id
        int v = ver[i];
        int L = edge[i];
        if(v == sl || v == sr)
            continue;
        if(v == prev)
            continue;
        long long max_d = dfs2(v, ans, sl, sr, u);
        if(max_d + L > max1)
        {
            max2 = max1;
            max1 = max_d + L;
        }
        else if(max_d + L > max2)
            max2 = max_d + L;
        ans = max(ans, max1 + max2);
    }
    return max1;
}

long long solve(const int N, const int s, vector<int>& visited, vector<long long>& d)
{
    vector<int> circle;
    vector<int> dist;
    vector<Edge> path;
    // 搜索环
    dfs1(s, visited, circle, dist, path);

    int t = circle.size();
    long long ans1 = 0; // 第一种情况
    for(int i = 0; i < t; ++i)
    {
        int si = circle[i];
        int sl = circle[(i + t - 1) % t];
        int sr = circle[(i + 1) % t];
        // 树的直径
        d[si] = dfs2(si, ans1, sl, sr, -1);
    }

    // circle[i..j]：d[circle[i]] + d[circle[j]] + dist[i, j] 的最大值
    // 枚举 j，找一个 max(0, j - t + 1) <= i <= j - 1，使得 d[circle[i]] + d[circle[j]] + sums[j] - sums[i] 最大
    circle.insert(circle.end(), circle.begin(), circle.end());
    dist.insert(dist.end(), dist.begin(), dist.end());
    vector<long long> sums(t * 2 + 1);
    for(int i = 1; i <= t * 2; ++i)
        sums[i] = sums[i - 1] + dist[i - 1];

    deque<int> deq;
    deq.push_back(0);
    long long ans2 = 0; // 第二种情况
    for(int j = 1; j < t * 2; ++j)
    {
        // deq 中是 [max(0, j - t + 1), j - 1]

        // 更新答案
        ans2 = max(ans2, d[circle[j]] + sums[j] + d[circle[deq.front()]] - sums[deq.front()]);

        // 插入 j 保持单调性
        while(!deq.empty() && d[circle[deq.back()]] - sums[deq.back()] <= d[circle[j]] - sums[j])
            deq.pop_back();
        deq.push_back(j);

        // 弹出 <=
        if(!deq.empty() && deq.front() < j - t + 2)
            deq.pop_front();
    }

    return max(ans1, ans2);
}

int main()
{
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();

    int N;
    cin >> N;
    for(int i = 1; i <= N; ++i)
    {
        int a, L;
        cin >> a >> L;
        add(i, a, L, i);
        add(a, i, L, i);
    }

    long long ans = 0;
    vector<int> visited(N + 1);
    vector<long long> d(N + 1);
    for(int s = 1; s <= N; ++s)
    {
        if(visited[s] == 0)
        {
            ans += solve(N, s, visited, d);
        }
    }

    cout << ans << endl;
}
Share