浅谈基环树

I_LOVE_MATH · 2025-07-28 21:24:21 · 算法·理论

浅谈基环树

更好的阅读体验

定义

对于一个连通图图 G，如果其点数与边数相等，那我们便称它为一个基环树。

也就是说，在一棵树上加一条边，就形成了一棵基环树。

一般地，如果图 G 不连通，其点数与边数相等，那么肯定就是若干个基环树的组合，称之为基环森林。

我们通常将基环树分为以下几类：

无向基环树：基环树由无向边连接。
内向基环树：基环树由有向边连接，每个节点出度都为 1。
外向基环树：基环树由有向边连接，每个节点入度都为 1。

不同的基环树，我们都有不同的处理方法，选对处理方法往往能够事半功倍，具体会在下面例题中讲到。

思路

对于一棵基环树的问题，我们通常有以下两种处理方法：

我们将一棵基环树视为一个环上面挂了很多子树，然后分别处理每一个子树，将信息合并到在环上的根上，把一棵基环树问题转化为一个在环上的问题
我们将一棵基环树视为一个多了一条边的树，可以先将这一边删掉，将其转化为树上问题，之后我们再考虑加上这条边造成的影响，将之前的结果加上影响即可

例题

P2607 [ZJOI2008] 骑士 link

题目大意

给出一个 n（1 \le n \le 10^6）个点的带点权的基环森林，求这个基环森林的最优独立集。

最优独立集：选出若干个点，使其两两之间没有连边，最大化这些点的点权和。

解题思路

我们将一个骑士和他痛恨的骑士连边，由于两者间只要选一个另一个就不能选，所以可以连无向边，因此这就构成了一个无向基环森林。

对于每一棵基环树，我们都求出它的最优独立集，最后相加即可。

现在我们先考虑思路 2。

首先，我们需要找到这棵基环树的环，将其上的一条边断掉，也就是说只需要求环上的一条边即可。

无向基环树找环需任选一点为根，进行 dfs，访问过的点都进行标记，直到经过一条边到达的点已经标记过，就说明这条边在环上，记录即可。

代码实现上有很多点要注意，由于存在二元环的情况，即父子之间成环，也就是说父子之间有两条边，我们删除环上一条边后，仍然可以通过第二条边到达父亲。

这说明我们不能使用点判断是否重复走，也就是不能使用 v != fa[v]，因为这样会导致 v 不能通过另一条边到达 fa[v]，所以需要通过边来判断，即走的这条边是否和上一条边相同。

具体地，我们使用链式向前星加边时对应双向边的编号是相邻的，这样我们就令编号从 2 开始，使得边 i 的对应边即为 i ^ 1，再在 dfs 时记录上一次经过的边 pre，通过 (i ^ 1) != pre 判断是否经过是否经过上一次经过的边。（如果链式向前星一开始初始化为 0 就不能让编号从 0 开始，因为 0 号会被认为是没有边）

同理，在之后的 dp 中，我们判断是否经过删除的那条边时也不能用点判断，要记录删除的边的编号通过边判断。

这样，记录了删除的边之后，确保每次不经过这条边，便可以开始树形 dp：

状态表示：dp_{i,0/1} 表示以 i 为根的子树内，不选/选 i 号节点，其最大独立集的大小。
初始化：dp_{i,0} = 0，dp_{i,1} = a_i（a_i 为 i 的权值）
状态转移
- 不选 i：则儿子无限制，即 dp_{i,0} = \sum{\max(dp_{son,1},dp_{son,0})}
- 选 i：则儿子都不能选，即 dp_{i,1} = \sum{dp_{son,0}}
答案：\max(dp_{root, 0},dp_{root, 1})

最后考虑删除的边 (u, v) 造成的影响。

删除后，有可能两者都选，不符合题意，因此我们要使其最多只选一个。

可以先钦定 u 不选，以 u 为根跑一遍 dp，再钦定 v 不选，以 v 为根跑一遍 dp，这使得至少有一个不选，最后我们合并两者的答案，\max(dp_{u, 0}, dp_{v, 0}) 即为答案。

另外，本题也可以使用思路 1，将每个子树 dp 后再在环上 dp，但很显然其实现难度大于思路 2，故不再赘述。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

struct edge
{
    int to, next;
} e[N << 1];

int n, tot = 2, ui, vi, ei;
int h[N], a[N];
ll dp[N][2], ans;
bool vis[N];

void add(int u, int v)
{
    e[tot].to = v;
    e[tot].next = h[u];
    h[u] = tot++;
}

void find_circle(int u, int pre)
{
    vis[u] = 1;
    for (int i = h[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if ((i ^ 1) != pre)
        {
            if (vis[v])
            {
                ui = u, vi = v, ei = i | 1;
                continue;
            }
            find_circle(v, i);
        }
    }
}

void dfs(int u, int pre)
{
    dp[u][0] = 0, dp[u][1] = a[u];
    for (int i = h[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if ((i ^ 1) != pre && (i | 1) != ei)
        {
            dfs(v, i);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int v;
        cin >> a[i] >> v;
        add(i, v);
        add(v, i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            continue;
        }
        find_circle(i, -1);
        dfs(ui, -1);
        ll tmp = dp[ui][0];
        dfs(vi, -1);
        ans += max(tmp, dp[vi][0]);
    }
    cout << ans << endl;
    return 0;
}

P4381 [IOI 2008] Island link

题目大意

给出一个 n（2 \le n \le 10^6）个点的带边权的基环森林，求所有基环树的直径之和。

直径：基环树中距离最远的两点间的距离。

解题思路

一棵树加上一条边后，其直径难以基于原来的直径算出，因此我们考虑思路 1。

先分类讨论，基环树的直径可以分为以下两种情况：

直径不经过环（环上的边都不在直径上）：将所有的子树的直径求出取最大值即可。
直径经过环（存在环上的边在直径上）：设 u,v 为环上两点，那么直径一定能表示为 d_u + d_v + dis(u, v)，其中 d_i 表示 i 子树内离 i 最远的点到 i 的距离（该子树的最大深度），dis(u, v) 表示 u 和 v 在环上的距离。

我们主要是要解决出下面那种情况。

同样是思路 1，一般有两种实现方式：树形 dp与拓扑排序，下面都会讲解。

法 1

建双向边，构成一个无向基环森林。

同样地，我们先找环，这一次我们需要求出具体的环，因为 dis(u,v) 是由若干条边组成的，并且记录边我们拥有的信息更多，所以我们需要将所有的边都记录在数组中。

我们仍然采用 dfs，但由于要记录每一条边，实现会有些许不同。

我们记录其 dfn 序以代替打标记，如果我们从 u 走到了一个已经访问过的点 v，还需判断是否 dfn_v > dfn_u，这保证了我们只允许从前辈访问后辈的时候再记录环，否则环会被记录两遍（后辈访问前辈也会记录一遍）。
我们预处理数组 pre_i，表示 i 是他的父亲由 pre_i 这条边到达 i 的，这使得当前辈 u 经过一条边到一个已经访问过的后辈 v 时，只需让 v 一直沿着 pre_i 走，边走边将 pre_i 放入数组，直到到达 u 就停止（特别地，我们可以将这条多出来的 (u, v) 放在数组的 0 号）。
找环时还应将所有环上的点进行标记，避免 dp 时跑到环上的其他点。

找到环上的所有边后，我们对这个环上的每个点，以其为根进行树形 dp，求出 d_i，顺便处理分类讨论的第一种情况，记第一种情况的最长直径为 mx，每次在更新 d_i 前，令 mx = \max(mx, d_i + d_{son} + w(i,son)) 即可。

现在我们考虑处理这个环上问题，即对环上两点 u,v，求 \max(d_u + d_v + dis(u, v))。

可以破环成链复制一份后跑单调队列 dp，但这里介绍一个更加简单的方法。

我们仍然破环成链，记 s_i 为前 i 条边的前缀和，l_i、r_i 为第 i 条边的左端点和右端点，len 为环的长度。

那么最大值可以分为以下两种情况：

res1 = \max(d_{l_i} + d_{l_j} + s_i - s_j) = \max(d_{l_j} - s_j) + d_{l_i} + s_i

res2 = \max(d_{l_i} + d_{l_j} + len - (s_i - s_j)) = \max(d_{l_j} - s_j) + d_{l_i} + len - s_i

由于我们是枚举 i 的，可以将一些常值提出，也就是说我们只需预处理 \max(d_{l_j} - s_j)、\max(d_{l_j} - s_j) 加上即可以做到 O(n) 复杂度。

答案即为 \max(mx, res1, res2)。

法 2

我们只连单向边，构成一个内向基环森林。

然后我们进行拓扑排序，将度为 0 的点放入队列，之后就按拓扑排序的方式走，出队后用自身信息更新父亲节点，然后进行标记。

可以发现，只有环上的点不会进入队列，也就是不会被标记，并且通过拓扑排序我们已经将子树的信息都合并到的环上，最后我们只剩下了若干个环需要处理。

接着对每个环计算第二种情况的结果即可，法 1 中已经提到了。

可以看到，拓扑排序是一种很好的处理基环树问题的方法，其码量要小于前者。

代码实现

法 1

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

struct edge
{
    int from, to, w, next;
} e[N << 1];

int n, tot = 2;
int h[N], pre[N];
int dfn[N], dfc;
bool vis[N];
int lp[N], cnt;
ll ans, mx, d[N], s[N];

void add(int u, int v, int w)
{
    e[tot].from = u;
    e[tot].to = v;
    e[tot].w = w;
    e[tot].next = h[u];
    h[u] = tot++;
}

void find_circle(int u)
{
    dfn[u] = ++dfc;
    for (int i = h[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if ((i ^ 1) == pre[v])
        {
            continue;
        }
        if (!dfn[v])
        {
            pre[v] = i;
            find_circle(v);
            continue;
        }
        if (dfn[v] < dfn[u])
        {
            continue;
        }
        vis[v] = 1;
        lp[0] = i ^ 1;
        while (v != u)
        {
            lp[++cnt] = pre[v];
            vis[e[pre[v]].from] = 1;
            v = e[pre[v]].from;
        }
    }
}

void dfs(int u)
{
    vis[u] = 1;
    for (int i = h[u]; i; i = e[i].next)
    {
        int v = e[i].to, w = e[i].w;
        if (!vis[v])
        {
            dfs(v);
            mx = max(mx, d[u] + d[v] + w);
            d[u] = max(d[u], d[v] + w);
        }
    }
}

ll solve(int x)
{
    mx = dfc = cnt = 0;
    find_circle(x);
    dfs(e[lp[0]].from);
    ll len = e[lp[0]].w;
    for (int i = 1; i <= cnt; i++)
    {
        dfs(e[lp[i]].from);
        s[i] = s[i - 1] + e[lp[i]].w;
    }
    len += s[cnt];
    ll res1 = -1e18, res2 = -1e18, mx1 = -1e18, mx2 = -1e18;
    for (int i = 1; i <= cnt; i++)
    {
        mx1 = max(mx1, d[e[lp[i]].to] - s[i - 1]);
        mx2 = max(mx2, d[e[lp[i]].to] + s[i - 1]);
        res1 = max(res1, mx1 + d[e[lp[i]].from] + s[i]);
        res2 = max(res2, mx2 + d[e[lp[i]].from] - s[i]);
    }
    return max(mx, max(res1, res2 + len));
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        add(i, v, w);
        add(v, i, w);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            ans += solve(i);
        }
    }
    cout << ans << endl;
    return 0;
}

法 2

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

int n;
int fa[N], w[N], deg[N];
queue<int> q;
ll d[N], dp[N], ans;

void topo()
{
    for (int i = 1; i <= n; i++)
    {
        if (!deg[i])
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        dp[fa[x]] = max(dp[fa[x]], max(dp[x], d[fa[x]] + d[x] + w[x]));
        d[fa[x]] = max(d[fa[x]], d[x] + w[x]);
        if (!(--deg[fa[x]]))
        {
            q.push(fa[x]);
        }
    }
}

ll solve(int x)
{
    ll len = w[x], res1 = dp[x], res2 = -1e18, mx1 = d[x], mx2 = d[x];
    int st = x;
    deg[x] = 0;
    x = fa[x];
    while (x != st)
    {   
        deg[x] = 0;
        res1 = max(res1, max(dp[x], d[x] + len + mx1));
        res2 = max(res2, d[x] - len + mx2);
        mx1 = max(mx1, d[x] - len);
        mx2 = max(mx2, d[x] + len);
        len += w[x];
        x = fa[x];
    }
    return max(res1, res2 + len);
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> fa[i] >> w[i];
        deg[fa[i]]++;
    }
    topo();
    for (int i = 1; i <= n; i++)
    {
        if (deg[i])
        {
            ans += solve(i);
        }
    }
    cout << ans << endl;
    return 0;
}

P3472 [POI 2008] MAF-Mafia link

题目大意

有 n（1 \le n \le 10 ^ 6）个人，每个人都用枪指着一个人（可以是自己），给出每个人用枪指着的人，之后按照需按照一定顺序开枪，求可能的最小和最大的死亡人数。

解题思路

每个人与他指着的人建单向边，形成一个内向基环森林。

由于思路 1 并不能很好地解释，我们仍然采取思路 2 的观点，即把基环树看作挂着许多子树的环。

我们先分析最大值，考虑一个环，最少只有一个人活下来（特别地，自环的话是可以全部死亡，需要特判）。

我们再考虑一棵树，叶子节点一定不死，因为没有人指着他们，然后如果想要更多人死，那就要尽可能在一个人死之前就开枪，于是我们可以从根的儿子先开始开枪，然后一层一层地开枪，最后只有叶子会活下来。

那么，结合两种观点，如果这个环上有子树的话，先让环开枪，最后只让这个有子树的点活下来，最后让所有子树按照层数开枪，环上的那个点会死掉，其他不是叶子的也会死，也就是这棵子树只有叶子活下来。

所以，最大值可以分三种情况：

自环：没人活。
环：活一个。
基环树：叶子活下来。

所有基环树存活数加起来，就能求得最小存活数，也就是最大死亡数。

我们再来分析最小值，根据上面的分析可以知道，叶子节点一定活下来。

递推可知，叶子节点的父亲必死，那么叶子节点的爷爷如果没有其他叶子指着就能活下来，然后一层层推广开来。

我们使用贪心思想，如果一个点是必死的，那我们绝对不让他在死前开枪，这一定是不优的，因为这个人的死亡最多能使其指向的点从死转到活，并不能使两个及以上的点由死到活以达到更优。

于是，我们可以发现活与死的等价条件：

活等价于是叶子或者指向他的点都死亡。
死等价于有活的点指向他。

基于这两个条件，我们可以采用递推的思想，一开始叶子的状态一定是确定的，然后让叶子去更新叶子父亲，叶子父亲去更新叶子爷爷，以此类推。

实现我们可以采取类似于拓扑排序的操作，先将度为 0 的点也就是叶子入队，然后每次次取出队首，更新其指向点的信息：

队首状态是死：将其指向的点的入度减 1，如果其指向点入度为 0，就将其标记为活，入队。
队首状态是活：如果他指向的点状态不是死，也就是说他还没被打死，就将其标记为死，同时更新最小死亡数，入队（我们不去修改它的度数，因为这使得其度数绝对不会被减到 0，避免前面将其起死回生的情况）。

如此以来，最后还可能有一些状态没有确定的点，这些点只有可能是其中任何一个点都没有被标记必死的环（如果一个环有点被其儿子标上必死，那么这个环就被打开了一个缺口，最后整个基环树的状态都能被确定）。

所以，我们再遍历所有点，如果这个点状态没有确定，就一直往其指着的点走，遍历这个环，并且都标记其状态，最后找出次环的长度，对于一个环，其最大存活数显然为 \frac{len}{2}，加上即可。

代码实现上，最小值可以和最大值一起处理，只需在进行拓扑排序时记录一个 vis 表示此环有没有环外的子树，最后在遍历环时将所有 vis 取或，为 0 就说明此环没有子树，需要将最大死亡数减 1。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

int n, cnt;
int p[N], deg[N], st[N];
int ans1, ans2;
bool vis[N];
queue<int> q;

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    ans1 = ans2 = n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        deg[p[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!deg[i])
        {
            ans1--, ans2--;
            st[i] = 1;
            vis[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[p[x]] = 1;
        if (st[x] == 1)
        {
            if (st[p[x]] == 2)
            {
                continue;
            }
            st[p[x]] = 2;
            q.push(p[x]);
        }
        else
        {
            if (--deg[p[x]])
            {
                continue;
            }
            st[p[x]] = 1;
            q.push(p[x]);
            ans1--;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            int len = 0;
            bool flag = 0;
            for (int j = i; !st[j]; j = p[j])
            {
                len++;
                flag |= vis[j];
                st[j] = 1;
            }
            ans1 -= len / 2;
            ans2 -= (flag ^ 1) && (len != 1);
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}

P10933 创世纪 link

题目大意

给出一个有向基环森林，选出若干点，要求所有选出的点都必须要有一个没被选出的点指向它，最大化选出点数。

解题思路

同样地，这道题也可以考虑思路 1，但是思路 2 还是更加简便。

这道题连边上有些文章可作，我们将集成内向基环树与外向基环树的优点，进行连边。

具体地，记 u 指向 v，我们用数组 p 记录一个点指向的点即 p_u = v，这是内向基环树；我们再用链式向前星由 v 向 u 建单向边，这是外向基环树。

这么连边的好处是操作方便，内向基环树优点是找环方便，由于点都是向内指的，只需随便选一个点一直往其指向的点走，直到重复为止便找到了环；而链式向前星建单向边的好处是方便 dp，删去环上一边后，以断点为根，每个节点其连边都是儿子。

上面已经说过了找环方法，将边断掉之后便可以开始树形 dp：

状态表示：dp_{i,0/1} 表示在以 i 根的子树内，i 不选 / 选时的最大选点数。
初始化：dp_{i,0/1}=0
状态转移
- 不选 i：则其子节点不受限制，即
  dp_{i,0}=\sum_{j \in son_i}{\max(dp_{j,0},dp_{j,1})}
- 选 i：则其子节点至少有一个不选，即
  dp_{i,1}=1+\max_{j \in son_i}{(dp_{j,0}+\sum_{k \in son_i,k \neq j}{\max(dp_{k,0},dp_{k,1})})}
  复杂度较高，考虑优化，发现右边的和式与 dp_{i,0} 很相似，于是有：
  \begin{aligned}dp_{i,1} &= 1+\max_{j \in son_i}{(dp_{j,0}+dp_{i,0} - \max(dp_{j,0},dp_{j,1}))} \\ &= 1 + dp_{i,0} - \min_{j \in son_i}{(\max(dp_{j,0},dp_{j,1}) - dp_{j,0})}\end{aligned}
  即可快速转移。
答案：\max(dp_{rt,0},dp_{rt,1})

现在我们考虑删去边的影响，原来有一条边是由根指向一个节点的，但是被删除了，这意味者原来根是可以限制此节点的，现在不行了，也就是说我们要考虑根限制此节点的情况。

于是我们再跑一遍 dp，钦定选根节点，即这个点已经被限制住了，意味着就算选这个点其儿子也不受任何限制，只需将选这个点的 dp 值加上 \min_{j \in son_i}{(\max(dp_{j,0},dp_{j,1}) - dp_{j,0})} 即可，最后答案为 dp_{rt,1}，与上面得到答案取最大值便得到了最终答案。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

struct edge
{
    int to, next;
} e[N];

int n, tot, rt, ans;
int a[N], h[N];
int dp[N][2];
bool vis[N];

void add(int u, int v)
{
    tot++;
    e[tot].to = v;
    e[tot].next = h[u];
    h[u] = tot;
}

void dfs(int u, bool flag)
{
    dp[u][0] = 0;
    vis[u] = 1;
    int mn = 1e9;
    for (int i = h[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v != rt)
        {
            dfs(v, flag);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            mn = min(mn, max(dp[v][0], dp[v][1]) - dp[v][0]);
        }
    }
    dp[u][1] = 1 + dp[u][0] - mn;
    if (flag && u == a[rt])
    {
        dp[u][1] += mn;
    }
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(a[i], i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            for (rt = i; !vis[rt]; rt = a[rt])
            {
                vis[rt] = 1;
            }
            dfs(rt, 0);
            int tmp = max(dp[rt][0], dp[rt][1]);
            dfs(rt, 1);
            ans += max(tmp, dp[rt][0]);
        }
    }
    cout << ans << endl;
    return 0;
}