基环树

算法

基环树就是「一棵树再多一条边」，因此 nn 个点 nn 条边的连通图恰好只有一个环。所有题目的第一步都是把那个环找出来：环上的每个点都是挂在它上面的那棵树的根，于是「环上怎么处理」和「树上怎么处理」可以分开做。

阅读前建议先掌握 树的入门 和 拓扑排序。环的判定与提取本质上是 DFS 与拓扑排序的应用，找环的更多写法见 找环。

1 什么是基环树

一棵树有 nn 个点、n−1n-1 条边。如果往树上再加一条边，就会出现唯一一个环——这样得到的图叫基环树。

反过来也成立：如果一个连通无向图有 nn 个点、nn 条边，那么它一定恰好含有一个环。这个「点数 = 边数」的判定非常好用，读题时一眼就能认出基环树。

左：无向基环树，红色是唯一的环，其余节点挂在环上；右：内向基环树，每个点只有一条出边

结构上可以这样理解：

基环树 = 一个环 + 环上每个点挂着一棵树⏟这些树与环只交于那个根 \text{基环树}\ =\ \text{一个环}\ +\ \underbrace{\text{环上每个点挂着一棵树}}_{\text{这些树与环只交于那个根}}

把环上的点记作 c1,c2,…,ckc_1,c_2,\dots,c_k。删掉环上的所有边之后，图会裂成 kk 棵树，树的根恰好是环上的点。这就是基环树题的基本分解方式。

1.1 三种常见形态

形态 判定 结构 典型题
无向基环树 nn 点 nn 边的连通无向图 环 + 挂树 基环树直径、基环树 DP
内向基环树 每个点出度 = 1 环 + 指向环的树（箭头朝环） luogu P2921、luogu P2607
外向基环树 每个点入度 = 1 环 + 从环长出的树（箭头离环） 少单独作考点，常由内向基环树反向建图得到

内向与外向互为反图：把每条边反向，内向就变成外向。所以真正要写的只有内向那一套——外向的题反向建图就归约过来了（实测见下文「内向基环树」一节）。

说明

名称容易记反，抓一条就好：判断依据是「环上的边朝哪边」。

  • 每个点都往外（指向环）有一条出边 → 内向；
  • 每个点都从环（离环）收到一条入边 → 外向。

题目给的数据往往是「每个点选一个后继」这种形式，那就是每点一条出边，属于内向。

有些题解会把 luogu P2607 叫做「基环外向树」，那是因为它们先反向建图再做树形 DP。两种叫法只差一个反图，但只要你自己统一口径就不会混。

注意

「nn 点 nn 边」只是基环树的必要条件，不是充分条件。如果图不连通，nn 点 nn 边会得到基环树森林（若干个基环树各贡献一个环，也可能有孤立环）。很多题（如 luogu P2607）的数据就是基环树森林，要对每个环分别处理再汇总。

2 核心套路：先找环，再把环当「根」

几乎所有基环树题都遵循同一个三步流程：

1. 找出环上的点（和环上的边）
2. 把每个环上点的挂树处理掉（通常是树上 DP / DFS）
3. 处理环本身

第 3 步是真正有变化的地方，常见的有三种：

手法 做法 适用
断环成链 在环上挑一条边断开，图就变成树了；但断掉的边可能被用到，所以要么枚举、要么对断点两端分类讨论 环上 DP、最大权独立集
破环成倍长链 把环复制一份接在后面，用前缀和 + 单调队列计算环上两点间的最远/最优 基环树直径
缩点 把整个环缩成一个点，得到一棵树，在树上做 求距离、计数类

其中「断环成链」最容易理解也最容易写错。以最大权独立集为例：断掉环上一条边 (c1,ck)(c_1, c_k) 之后图成了树，可以直接树上 DP。但断掉的那条边原本约束着 c1c_1 和 ckc_k 不能同时选，所以要把这个约束补回来——常见做法是强制 c1c_1 不选和强制 ckc_k 不选各跑一遍，取较大值。

3 找环

「找环」是基环树题的入口。这里给两种思路，建议先读第一种——它不更短（两版行数接近），但明显更好懂，而且无向基环树和内向基环树用的是同一个想法。

一、 剥叶法（推荐先看）

核心只有一句话：反复删掉度数为 1 的点，剥到最后剩下的必然全是环上的点。

为什么？环上的每个点至少和环上两个邻居相连，度数永远降不到 1；而环外的点都是挂在环上的树，一棵树最外层的叶子度数为 1，删掉它之后上一层就可能变成新叶子，于是从外往里一层层剥干净。

剥叶三步：先剥掉叶子 6、7，5 变成新叶子；再剥掉 5，剩下每个点度数都是 2，剥不动了

代码就是一个队列加一个「沿环走一圈」：

#include <bits/stdc++.h>
using namespace std;

// 无向基环树找环：剥叶法。
// 核心只有一句话：反复删掉度数为 1 的点（叶子），
// 剥到最后剩下的点必然全都待在环上。
// 输出格式与 find_cycle.cpp（DFS 版）完全一致，方便逐行对照。
// 约定：n 个点 n 条边的连通无向图（可以有重边，但环长至少为 2）。
const int maxn = 200000 + 5;

int n, m;

/*------------------------ 存图 开始 ------------------------*/
struct Edge {
    int to; // 边指向的点
    int w;  // 边权
    int id; // 这条有向边的编号；成对存放时 id 与 id^1 互为反向边
};

vector<Edge> g[maxn];
int ecnt;

void add_edge(int u, int v, int w) {
    g[u].push_back({v, w, ecnt++});
    g[v].push_back({u, w, ecnt++});
}
/*------------------------ 存图 结束 ------------------------*/

/*------------------------ 剥叶法找环 开始 ------------------------*/
int deg[maxn];     // deg[u]：u 当前的度数，剥叶过程中会不断减小
bool on_cyc[maxn]; // on_cyc[u]：u 还没被剥掉，也就是最终留在环上

long long cyc_sum; // 环上边权之和
vector<int> cyc_v; // 环上的点，按环的顺序存放
vector<int> cyc_w; // cyc_w[i]：cyc_v[i] 到 cyc_v[i+1]（末项回到 cyc_v[0]）的边权

void find_cycle() {
    // 第一步：剥叶。度数变成 1 的点就是叶子，删掉它会让邻居的度数再减一。
    queue<int> q;
    for (int u = 1; u <= n; ++u) {
        on_cyc[u] = true;
        if (deg[u] == 1) q.push(u);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        on_cyc[u] = false; // u 不是环上的点
        for (const Edge &e : g[u]) {
            int v = e.to;
            if (!on_cyc[v]) continue;       // 这个邻居已经被剥掉了，不用管
            if (--deg[v] == 1) q.push(v);   // v 变成了新的叶子
        }
    }

    // 第二步：剩下的一定是环，沿环走一圈，记录顺序和每条环边的权值。
    int start = 0;
    for (int u = 1; u <= n; ++u) {
        if (on_cyc[u]) {
            start = u;
            break;
        }
    }

    cyc_sum = 0;
    int pre_id = -1; // 刚走过的那条边的编号；用 pre_id^1 跳过它的反向边
    int cur = start;
    do {
        cyc_v.push_back(cur);
        for (const Edge &e : g[cur]) {
            if (!on_cyc[e.to]) continue;              // 只走环上的点
            if (e.id == (pre_id ^ 1)) continue;       // 不走刚来的那条边，重边也不会走回头
            cyc_w.push_back(e.w);
            cyc_sum += e.w;
            pre_id = e.id;
            cur = e.to;
            break;
        }
    } while (cur != start);
}
/*------------------------ 剥叶法找环 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        ++deg[u];
        ++deg[v];
    }

    find_cycle();

    int cyc_n = (int)cyc_v.size();
    cout << cyc_n << '\n';
    for (int i = 0; i < cyc_n; ++i) {
        cout << cyc_v[i] << ' ' << cyc_v[(i + 1) % cyc_n] << ' ' << cyc_w[i] << '\n';
    }
    cout << cyc_sum << '\n';
    return 0;
}

对比一下它省掉了什么：没有递归、没有时间戳、没有父亲数组，也不需要理解「非树边一定连向祖先」这种 DFS 性质。整段就是「读度数 → 剥叶子 → 走一圈」。

注意

剥叶法依赖一个前提：整张图恰好只有一个环。它就是基环树的定义，所以对本文所有题目都成立。

但如果图里有多个环（不连通的基环树森林，或一般图），剥叶会把这些环全部保留下来——那时它只能告诉你「哪些点在某个环上」，不能直接给出某一个环的顺序。遇到这种情况请用下面的 DFS 法。

二、 内向基环树：同样是剥叶

内向基环树（每个点出度恰好为 1）把「剥叶」换一个说法就成型了：环外的点最终都会顺着出边走进环，所以只要不断删掉入度为 0 的点，剩下的就是环。

思路和上面完全一样，只是「叶子」的判定从「度数为 1」换成了「入度为 0」。

#include <bits/stdc++.h>
using namespace std;

// 内向基环树（每个点恰好一条出边，即函数图）：找环并求每个点的答案。
// 对应洛谷 P2921：从 i 出发沿 nxt 一直走，直到回到去过的点，问经过多少个点。
// 约定：n 个点 n 条边，nxt[u] 是 u 的唯一出边指向的点，允许自环。
const int maxn = 100000 + 5;

int n;
int nxt[maxn]; // nxt[u]：u 的唯一后继

/*------------------------ 内向基环树 代码 开始 ------------------------*/
int indeg[maxn]; // indeg[u]：u 的入度
bool in_cycle[maxn]; // in_cycle[u]：u 是否在环上
int cyc_len[maxn];   // cyc_len[u]：u 所在环的长度（只对环上的点有意义）
int ans[maxn];       // ans[u]：从 u 出发回到已访问点时经过的点的个数

vector<int> order; // 拓扑剥叶的出队顺序，环外的点都在里面

// 第一步：拓扑排序剥掉所有不在环上的点。
// 出度为 1 的图里，“入度能降到 0 的点”就是挂在环外面的点；
// 剥完之后只剩下环，剥不掉。
void peel() {
    queue<int> q;
    for (int u = 1; u <= n; ++u) {
        in_cycle[u] = true;
        if (indeg[u] == 0) q.push(u);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_cycle[u] = false; // 能出队就说明不在环上
        order.push_back(u);

        int v = nxt[u];
        if (--indeg[v] == 0) q.push(v);
    }
}

// 第二步：给环上的每个点标上它所在环的长度。
// 从任意一个还没标记的环上点出发绕一圈，走回自己就是整圈。
void mark_cycle_len() {
    for (int u = 1; u <= n; ++u) {
        if (!in_cycle[u] || cyc_len[u]) continue;

        int len = 0;
        int x = u;
        do {
            cyc_len[x] = 0; // 先占位，避免重复进入
            x = nxt[x];
            ++len;
        } while (x != u);

        x = u;
        do {
            cyc_len[x] = len;
            x = nxt[x];
        } while (x != u);
    }
}

// 第三步：环外的点逆着拓扑序递推。
// 因为它下一步一定走向 nxt[u]，而 nxt[u] 的答案此时已经算好。
void calc_answer() {
    for (int u = 1; u <= n; ++u) {
        ans[u] = in_cycle[u] ? cyc_len[u] : 0;
    }
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];
        ans[u] = ans[nxt[u]] + 1; // 走一步到 nxt[u]，再加上它之后的步数
    }
}
/*------------------------ 内向基环树 代码 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int u = 1; u <= n; ++u) {
        cin >> nxt[u];
        ++indeg[nxt[u]];
    }

    peel();
    mark_cycle_len();
    calc_answer();

    for (int u = 1; u <= n; ++u) {
        cout << ans[u] << '\n';
    }
    return 0;
}

这段代码顺便解决了一类题：求出每个点「沿出边一直走，到回到已访问点」的步数。环上的点答案是环长，环外的点递推 ans[u] = ans[nxt[u]] + 1，按拓扑序逆序处理即可。

三、 DFS + 时间戳（通用备选）

如果不想依赖「恰好一个环」这个前提，或者你的图是有向的一般图，就用标准的 DFS 找环。

在无向图上 DFS，所有非树边都连向祖先（没有横叉边）。所以一旦沿着某条边走到一个「时间戳更小的已访问点」，就发现了一个环：它是「当前点到该祖先」的树上路径，再加上这条回边。

#include <bits/stdc++.h>
using namespace std;

// 无向基环树找环：找出一棵树加一条边后形成的那个唯一环。
// 输出环上的点（按环的顺序）、每条环边以及环长。
// 约定：n 个点 n 条边的连通无向图（可以有重边，但环长至少为 2）。
const int maxn = 200000 + 5;

int n, m;

/*------------------------ 存图 开始 ------------------------*/
struct Edge {
    int to;   // 边指向的点
    int w;    // 边权
    int id;   // 这条有向边的编号；成对存放时 id 与 id^1 互为反向边
};

vector<Edge> g[maxn];
int ecnt; // 已存的边数（无向边记两条）

void add_edge(int u, int v, int w) {
    g[u].push_back({v, w, ecnt++});
    g[v].push_back({u, w, ecnt++});
}
/*------------------------ 存图 结束 ------------------------*/

/*------------------------ 找环 代码 开始 ------------------------*/
int dfn[maxn], timer; // dfn[u]：DFS 时间戳，0 表示未访问
int fa[maxn];         // fa[u]：DFS 树上的父亲
int faw[maxn];        // faw[u]：边 (fa[u], u) 的权值

int cyc_n;         // 环上的点数
vector<int> cyc_v; // 环上的点，按环的顺序存放
vector<int> cyc_w; // cyc_w[i]：cyc_v[i] 到 cyc_v[i+1]（末项回到 cyc_v[0]）的边权
long long cyc_sum; // 环上边权之和

// 找到回边 u -> v（v 是 u 的祖先）后，沿父亲指针把整条环拼出来。
void build_cycle(int u, int v, int back_w) {
    vector<int> tmp;
    // 从 u 一路回溯到 v，得到 [u, ..., v]
    for (int x = u; x != v; x = fa[x]) tmp.push_back(x);
    tmp.push_back(v);

    cyc_n = (int)tmp.size();
    cyc_v.resize(cyc_n);
    cyc_w.resize(cyc_n);
    // 反转成 [v, ..., u]，这样相邻两点之间就是一条环边
    for (int i = 0; i < cyc_n; ++i) cyc_v[i] = tmp[cyc_n - 1 - i];

    cyc_sum = 0;
    for (int i = 0; i + 1 < cyc_n; ++i) {
        cyc_w[i] = faw[cyc_v[i + 1]]; // cyc_v[i] -> cyc_v[i+1] 就是儿子那条父亲边
        cyc_sum += cyc_w[i];
    }
    cyc_w[cyc_n - 1] = back_w; // 最后一条是那条回边 u -> v
    cyc_sum += back_w;
}

// 返回 true 表示已经找到环，可以提前停止。
// in_id 是进入 u 的那条有向边的编号，用它跳过反向边 id^1，重边也不会误判。
bool dfs(int u, int in_id) {
    dfn[u] = ++timer;
    for (const Edge &e : g[u]) {
        if (e.id == (in_id ^ 1)) continue; // 不走刚来的那条边的反向
        int v = e.to;
        if (!dfn[v]) {
            fa[v] = u;
            faw[v] = e.w;
            if (dfs(v, e.id)) return true;
        }
        else if (dfn[v] < dfn[u]) {
            // 无向图 DFS 中，非树边一定连向祖先。
            // 只从时间戳大的一侧处理一次，避免同一个环被算两遍。
            build_cycle(u, v, e.w);
            return true;
        }
    }
    return false;
}
/*------------------------ 找环 代码 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    dfs(1, -1); // -1 ^ 1 == -2，不会等于任何合法边编号

    cout << cyc_n << '\n';
    for (int i = 0; i < cyc_n; ++i) {
        cout << cyc_v[i] << ' ' << cyc_v[(i + 1) % cyc_n] << ' ' << cyc_w[i] << '\n';
    }
    cout << cyc_sum << '\n';
    return 0;
}

几个关键点：

  • 用 in_id 记录「进来的那条有向边」的编号，跳过它的反向边（id ^ 1）。这样即使有重边也不会立刻走回去。
  • 只从时间戳大的一侧处理（dfn[v] < dfn[u]），否则同一个环会被从两端各算一次。
  • 沿父亲指针回溯时，环的边权就是「儿子那条父亲边」的权值；最后补上回边的权值。

3.4 两版怎么选

剥叶法 DFS + 时间戳
代码量 相近（都要走一圈拿环序） 相近
概念难度 低：队列 + 度数 中：非树边连祖先、时间戳方向、回溯拼接
前提 整图恰好一个环 无，一般图也能用
适用 基环树的全部题目 需要找「任意一个环」时

两版输出格式完全一致（环上点序 + 每条环边权 + 环长），可以互相替换着跑。

4 经典例题

一、 内向基环树 + 最大权独立集

luogu P2607

每个骑士有且仅有一个最厌恶的人，且两人不能同时入选。把「厌恶」看成一条从 ii 指向 hih_i 的有向边，每个点出度恰好为 1——这就是内向基环树森林。

弱化版是树上最大权独立集，也就是「没有上司的舞会」：设 f(u,0/1)f(u,0/1) 表示 uu 选/不选时子树内的最大和。

f(u,0)=∑v∈son(u)max⁡(f(v,0),f(v,1)),f(u,1)=wu+∑v∈son(u)f(v,0). \begin{aligned} f(u,0) &= \sum_{v \in \text{son}(u)} \max\bigl(f(v,0), f(v,1)\bigr),\\ f(u,1) &= w_u + \sum_{v \in \text{son}(u)} f(v,0). \end{aligned}

放到基环树上，就按前面说的断环：在环上挑一条边 (a,b)(a,b) 断开，分别以 aa、bb 为根各做一次树形 DP，各取「根不选」的答案 f[a][0] 与 f[b][0]，两者取 max。

为什么这样就够了？设最终方案为 SS。因为 a,ba,b 相邻，SS 里至少有一个不被选：若 a∉Sa\notin S，它的最优值被 f[a][0] 覆盖；若 b∉Sb\notin S，则被 f[b][0] 覆盖。两次 DP 都在「断开后的树」上做，只比原图少一条约束，所以结果一定合法。

注意本题是基环树森林，每个连通块算完再求和。完整的可运行代码见下面「五、城市环路」——那题就是这套做法的标准版本。

二、 内向基环树练手

luogu P2921

N≤105N\le 10^5，每个隔间贴了「下一个隔间」的标语，问从每个隔间出发、到第一次回到去过的隔间为止经过多少个隔间。就是上面 functional_cycle.cpp 的原题，数据里允许自环，本文模板已经覆盖。

三、 基环树直径

luogu P4381

N≤106N\le 10^6，给一个基环树森林（每座桥连一座岛），求各基环树直径之和。

直径只有两种可能：

  1. 不经过环：完全在某棵挂树内部。用普通树形 DP 求最长链即可。
  2. 经过环：设环上点 ii 的挂树中最长链为 fif_i，环上两点 i,ji,j 的距离为 d(i,j)d(i,j)，则候选值是
    max⁡i≠j(fi+fj+d(i,j)). \max_{i\ne j}\bigl(f_i+f_j+d(i,j)\bigr).

第 2 类需要破环成链：把环复制一遍接在尾部，用前缀和 ss 表示「从链首沿环走到当前位置的距离」，于是

d(i,j)=sj−si(i<j, j−i<k), d(i,j) = s_j - s_i \quad(i<j,\ j-i<k),

条件 j−i<kj-i<k 表示两点之间的路径不绕整圈。要最大化 fj+sj+(fi−si)f_j+s_j + (f_i - s_i)，对固定的 jj 只需维护前若干个 ii 中 (fi−si)(f_i-s_i) 的最大值——这正是单调队列的标准形式，环上部分 O(k)O(k) 完成。

NN 到 10610^6，递归 DFS 在链形数据上会爆栈，求环与求树 DP 都建议写成迭代或手工栈。

四、 枚举断边 + 贪心

luogu P5022: [NOIP 2018 提高组] 旅行

m=n−1m=n-1 时是纯树：从 11 出发，每次走向编号最小且未访问的邻居，就是字典序最小的 DFS 序。

m=nm=n 时是基环树：最终路线必然恰好少走环上的一条边。于是枚举删掉环上的哪一条边，每次当成树做一遍贪心 DFS，在所有方案里取字典序最小。因为环长最多为 nn，枚举 O(n)O(n) 次、每次 O(n)O(n)，总 O(n2)O(n^2)——在本题的数据范围内可以接受。

五、 城市环路

luogu P1453: 城市环路

这是「断环 + 树形 DP」的标准版本，第一题（luogu P2607）就是同一套代码换个输入。

本题输入是「点权 + 无向边」的单圈图，输出要把最大权值和乘上常数 kk 并保留一位小数。

#include <bits/stdc++.h>
using namespace std;

// 基环树最大权独立集：断环 + 树形 DP。对应洛谷 P1453 城市环路。
//
// 思路：环上任意一条边 (a,b) 断开后，图就成了一棵树，可以直接做「没有上司的舞会」。
// 但断掉的那条边原本禁止 a、b 同时被选，所以分两次 DP 把这个约束补回来：
//   第一次以 a 为根，取 a 不选的答案 f[a][0]  (a 不选，则 (a,b) 自然满足)
//   第二次以 b 为根，取 b 不选的答案 f[b][0]  (b 不选，同上)
// 任何一个合法方案必然有「a 不选」或「b 不选」，所以两者取 max 就是答案。
//
// 约定：n 个点 n 条边的连通无向图（单圈图），点编号 0..n-1。
const int maxn = 100000 + 5;

int n;
long long p[maxn]; // p[u]：u 的点权（人流量）

/*------------------------ 存图 开始 ------------------------*/
struct Edge {
    int to; // 边指向的点
    int id; // 这条有向边的编号；成对存放时 id 与 id^1 互为反向边
};

vector<Edge> g[maxn];
int ecnt;

void add_edge(int u, int v) {
    g[u].push_back({v, ecnt++});
    g[v].push_back({u, ecnt++});
}
/*------------------------ 存图 结束 ------------------------*/

/*------------------------ 断环 + 树形DP 开始 ------------------------*/
int deg[maxn];     // deg[u]：u 当前的度数，剥叶过程中会减小
bool on_cyc[maxn]; // on_cyc[u]：u 还没被剥掉，也就是最终留在环上

int cut_id; // 被断开的环边编号
int cut_a;  // 被断边的两个端点
int cut_b;

// 第一步：剥叶找环，然后随便挑一条「两端都在环上」的边作为要断的边。
// 注意必须记录边而不是只记录两个端点：二元环（两点之间两条边）时，
// 只按端点删会把两条边一起删掉。
void find_cut_edge() {
    queue<int> q;
    for (int u = 1; u <= n; ++u) {
        on_cyc[u] = true;
        if (deg[u] == 1) q.push(u);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        on_cyc[u] = false;
        for (const Edge &e : g[u]) {
            if (!on_cyc[e.to]) continue;
            if (--deg[e.to] == 1) q.push(e.to);
        }
    }

    cut_id = -1;
    for (int u = 1; u <= n && cut_id < 0; ++u) {
        if (!on_cyc[u]) continue;
        for (const Edge &e : g[u]) {
            if (!on_cyc[e.to]) continue;
            cut_id = e.id;
            cut_a = u;
            cut_b = e.to;
            break;
        }
    }
}

long long f[maxn][2]; // f[u][0]：u 不选；f[u][1]：u 选

// 第二步：在断边后的树上做最大权独立集。
// 跳过被断的那条边（正反两个编号都要跳）。
void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1] = p[u];
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == fa) continue;
        if (e.id == cut_id || e.id == (cut_id ^ 1)) continue; // 这条边已断
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]); // u 不选，儿子随意
        f[u][1] += f[v][0];               // u 选，儿子只能不选
    }
}

// 第三步：分别以两端为根各跑一遍，取「根不选」的较大值。
long long solve() {
    find_cut_edge();

    dfs(cut_a, 0);
    long long ans_a = f[cut_a][0];

    dfs(cut_b, 0);
    long long ans_b = f[cut_b][0];

    return max(ans_a, ans_b);
}
/*------------------------ 断环 + 树形DP 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i + 1]; // 题目编号 0..n-1，这里统一平移到 1..n
    }
    for (int i = 1; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u + 1, v + 1);
        ++deg[u + 1];
        ++deg[v + 1];
    }

    double k;
    cin >> k;

    long long best = solve();
    printf("%.1f\n", (double)best * k);
    return 0;
}

两处值得注意的细节：

  • 断边要记录「边」，不能只记录两个端点。 二元环（两点之间有两条边）时，按端点删会把两条边一起删掉，图就断了。模板里用 cut_id 与 cut_id ^ 1 精确跳过一条边。
  • 为什么取 f[root][0] 而不是 max(f[root][0], f[root][1])。 取 f[root][1] 等于允许根被选，而根恰好是被断边的端点，可能与另一端冲突。只取 f[root][0] 才保证这条约束一定成立。

5 易错点

  • 把「nn 点 nn 边」当成连通图。 它只能保证「环的个数 = 边数 − 点数 + 连通块数」，图不连通时请按基环树森林处理，对每个环分别算再汇总。
  • 无向图找环时不判反向边（两版都适用）。 一定要跳过 in_id ^ 1，否则重边（两点之间有两条边）会被误判成「立刻走回去」而找不到环。
  • 同一个环被算两遍（仅 DFS 版）。 回边要从时间戳大的一侧处理，只认 dfn[v] < dfn[u]。
  • 环的顺序搞反（仅 DFS 版）。 沿父亲回溯得到的是「从回边起点到祖先」的顺序，通常需要反转才能让「相邻两点之间是一条环边」。环边权与环上点要一一对齐，写错会得到随机错误。
  • 该用剥叶法时却写了 DFS。 基环树（含内向形态）用剥叶更省事，还顺带得到拓扑序，可以直接拿去递推答案；只有当图里可能有多个环、需要「任意找一个环」时才动用 DFS。
  • 剥叶法用在了多环图上。 它会把所有环一起保留下来，此时只能回答「哪些点在环上」，拿不到某一个环的顺序。
  • 自环没考虑。 内向基环树允许 nxtu=unxt_u = u，此时环长是 11；模板里绕一圈的写法能自然处理，但手写时要确认不会死循环。
  • 外向/内向弄混。 出度为 1 是内向（箭头朝环），入度为 1 是外向（箭头离环）。两者互为反图，做题前先确认题目给的是哪一个。
  • 断环后忘了补约束。 断掉的那条边仍然约束着两个端点，必须通过「强制某一端不选」跑两遍来补回来，只删不管会算大。
  • 基环树直径只算了经过环的情况。 挂在环上的树自己也可能藏着直径，两种都要取 max⁡\max。
  • 递归深度。 基环树常配 n≥105n\ge 10^5 的数据，链形挂树会让递归 DFS 达到 O(n)O(n) 深度，栈要留够或改迭代。

6 相关阅读

7 相关题解

暂无相关题解