当前位置： 首页 > news >正文

浅谈基环树

news 2025/7/29 12:48:29

浅谈基环树

定义

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

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

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

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

  • 无向基环树：基环树由无向边连接。

  • 内向基环树：基环树由有向边连接，每个节点出度都为 \(1\)。

  • 外向基环树：基环树由有向边连接，每个节点入度都为 \(1\)。

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

思路

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

  1. 我们将一棵基环树视为一个环上面挂了很多子树，然后分别处理每一个子树，将信息合并到在环上的根上，把一棵基环树问题转化为一个在环上的问题

  2. 我们将一棵基环树视为一个多了一条边的树，可以先将这一边删掉，将其转化为树上问题，之后我们再考虑加上这条边造成的影响，将之前的结果加上影响即可

例题

题目大意

给出一个 \(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;
}

题目大意

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

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

解题思路

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

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

  1. 直径不经过环（环上的边都不在直径上）：将所有的子树的直径求出取最大值即可。
  2. 直径经过环（存在环上的边在直径上）：设 \(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;
}

题目大意

有 \(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;
}

题目大意

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

解题思路

同样地，这道题也可以考虑思路 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;
}
http://www.sczhlp.com/news/722.html

相关文章：

  • Day 28
  • 2025.7.28
  • 《叔向贺贫》
  • 2025总结
  • AI绘画提示词
  • 记一个由tinyint类型引发的低级错误
  • Dify快速搭建问答系统
  • AGC050A AtCoder Jumper
  • 用 Python 构建可扩展的图像验证码识别模块
  • 带外安全更新深度解析：ATL漏洞与IE防御措施
  • 更多脚本详见csdn
  • 第三天
  • Golang基础笔记十五之sync
  • hot100 回溯算法
  • 7.28随笔
  • 外培总结
  • 7月28日
  • CodeBuddy IDE小试-单元测试篇
  • 《大道至简》
  • linux中常用的数值计算
  • 【问题】--Macbook相关问题
  • 软工作业day27
  • 2025.7.28 闲话：CF678E Another Sith Tournament 倒序状压 DP 的一点想法
  • 基础知识
  • java学习（大道至简读后感）
  • js基础第一天
  • 春训#1题解
  • 垃圾话1
  • 2025/7/28 总结
  • 7.27 周总结