基环树

基环树

定义

在树形结构中添加一条边形成的图。

分类

1. 无向图基环树
2. 内向基环树，每个点的出度为 1。
3. 外向基环树，每个点的入度为 1。

找环：

方法1：无向图基环树找环。

拓扑排序，去掉环以外的点，剩下的就是一个那个环。

方法2：有向图和无向图均适用。

原理：在搜索树中检查一个点 \(x\) 的子节点 \(son\) 是否深度更浅。

方法3：Tarjan 改造版本。

原理：从环上某点 \(x\) 沿着某个方向 \(y\)，当 \(x\) 沿另一侧到达点 \(y\) 时，会出现 \(dfn[y] > dfn[x]\)，说明是个环。

使用技巧

1. 把环当作根结点，分成环上的点和环上点的子树；
2. 把环斩断，变成 1 棵树处理。

例题

P2607 骑士

1. 每个点和其憎恨的点不能同时选择；
2. 连无向边，得到基环树；
3. 任意枚举一条环上的边以及其端点 \(x\) 和 \(y\)；
4. 分别从 \(x\) 和 \(y\) 跑一遍树形 DP 即可。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 1000010, M = 2000010;

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

int head[N], idx = 1;

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

int n, w[N];
bool vis[N];
int del = -1, del_u = -1, del_v = -1;

void dfs(int u, int last_edge) {
    // cout << u << endl;
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].next) {
        if (i == (last_edge ^ 1)) continue;
        int to = e[i].to;
        if (!vis[to]) dfs(to, i);
        else {
            del = i, del_u = e[i ^ 1].to, del_v = e[i].to;
            // cout << last_edge << endl;
            // cout << "SHA" << del_u << ' ' << del_v << endl;
        }
    }
}

i64 f[N][2];

void dfs2(int u, int last_edge) {
    // cout << u << ' ' << last_edge << endl;
    f[u][0] = 0, f[u][1] = w[u];
    for (int i = head[u]; i; i = e[i].next) {
        if (i == del || i == (del ^ 1) || i == (last_edge ^ 1)) continue;
        int to = e[i].to;
        dfs2(to, i);
        f[u][0] += max(f[to][1], f[to][0]);
        f[u][1] += f[to][0];
    }
}

int main() {
    // freopen("a.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int son;
        cin >> w[i] >> son;
        add(i, son);
        add(son, i);
    }

    i64 ans = 0;

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            del = -1, del_u = -1, del_v = -1;
            dfs(i, -1);
            // cout << del_u << ' ' << del_v << endl;
            i64 tmp = 0;
            dfs2(del_u, -1);
            tmp = max(tmp, f[del_u][0]);
            dfs2(del_v, -1);
            tmp = max(tmp, f[del_v][0]);
            ans += tmp;
        }
    }
    cout << ans << '\n';
    return 0;
}