• 考虑断开环上的边，转化为树上问题，最后考虑该边的影响
• 去掉环，此时每个点均构成一棵大小大于等于 $1$ 的子树，然后对环进行处理。

旅行，Luogu P5022

断边处理。

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 5010, M = 10010;

int n, m;
int dfn[N], fa[N], cnt;
int del[N][N];
vector<vector<int>> rings;
vector<int> ring;
vector<int> ans;
vector<int> g[N];

void add(int a, int b) {
    g[a].push_back(b);
}

void getring(int u) {
    dfn[u] = ++ cnt;
    for (int i = 0; i < g[u].size(); i ++ ) {
        int j = g[u][i];
        if (j == fa[u]) continue;
        if (!dfn[j]) {
            fa[j] = u;
            getring(j);
        }
        else if (dfn[u] < dfn[j]) {
            ring.clear();
            ring.push_back(j);
            do { ring.push_back(fa[j]), j = fa[j]; }
            while (j != u);
            rings.push_back(ring);
        }
    }
}

void dfs(int u, int fa) {
    ans.push_back(u);
    for (int i = 0; i < g[u].size(); i ++ ) {
        int j = g[u][i];
        if (j == fa) continue;
        if (del[u][j] || del[j][u]) continue;
        dfs(j, u);
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i ++ ) {
        int a = read(), b = read();
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i ++ ) sort(g[i].begin(), g[i].end());
    getring(1);
    vector<int> res(n, 1e9);
    if (rings.size() == 0) {
        dfs(1, 0);
        res = ans;
    }
    else {
        for (int i = 0; i < ring.size() - 1; i ++ ) {
            del[ring[i]][ring[i + 1]] = true;
            del[ring[i + 1]][ring[i]] = true;
            ans.clear();
            dfs(1, 0);
            if (ans < res) res = ans;
            del[ring[i]][ring[i + 1]] = false;
            del[ring[i + 1]][ring[i]] = false;
        }
    }
    for (int i = 0; i < res.size(); i ++ ) printf("%d ", res[i]);
    return 0;
}

Island 岛屿（AcWing & Luogu P4381）

基环树直径。

考虑去掉树上的环，答案有两种情况：

• 直径在某棵子树上
• 直径经过环上的边

对于第一种情况，答案为最大的子树的直径。

对于第二种情况，设 $a, b$ 分别为环上边的两端，则答案可以分割为三部分：$a, b$ 的长度，以 $a$ 为根从 $a$ 出发到达的最远距离（不经过环上的点），以 $b$ 为根从 $b$ 出发到达的最远距离（不经过环上的点）。

即 $dist_{a, b} + f_a + f_b$，时间复杂度 $O(n^2)$，不足以通过此题，将链上的距离做前缀和，原式变为 $sum_b - sum_a + f_a + f_b$。

可以使用单调队列优化。

关于双指针：待填坑

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 1000010, M = 2 * N;

int n, cnt, rt, res = 0, ans = 0;
int h[N], e[M], ne[M], w[M], idx;
int dfn[N], d[N], s[N], fa[N], q[N];
vector<int> ring;
bool vis[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void add_ring(int a, int b, int c) {
    ring.clear();
    s[1] = c;
    ring.push_back(b);
    s[2] = w[fa[b]];

    do {
        int u = e[fa[b] ^ 1];
        ring.push_back(u);
        s[ring.size() + 1] = w[fa[u]];
        b = e[fa[b] ^ 1];
    } while (a != b);

    int sz = ring.size();
    for (int i = 1; i <= sz; i ++ ) {
        vis[ring[i - 1]] = true;
        ring.push_back(ring[i - 1]);
        s[sz + i] = s[i];
    }

    for (int i = 1; i <= ring.size(); i ++ ) s[i] += s[i - 1];
}

void getring(int u, int f) {
    dfn[u] = ++ cnt;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        if (!dfn[j]) {
            fa[j] = i;
            getring(j, u);
        }
        else if (dfn[u] < dfn[j]) add_ring(u, j, w[i]);
    }
}

void dp(int u) {
    vis[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (vis[j]) continue;
        dp(j);
        res = max(res, d[u] + d[j] + w[i]);
        d[u] = max(d[u], d[j] + w[i]);
    }
}

int on_the_ring() {
    int hh = 0, tt = -1;
    int sz = ring.size() / 2;
    int tmp = 0;
    for (int i = 1; i <= 2 * sz; i ++ ) {
        while (hh <= tt && q[hh] < i - sz + 1) hh ++ ;
        if (hh <= tt) tmp = max(tmp, d[ring[i - 1]] + d[ring[q[hh] - 1]] + s[i] - s[q[hh]]);
        while (hh <= tt && d[ring[q[tt] - 1]] - s[q[tt]] <= d[ring[i - 1]] - s[i]) tt -- ;
        q[ ++ tt] = i;
    }
    return tmp;
}

signed main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 1; i <= n; i ++ ) {
        int b = read(), c = read();
        add(i, b, c), add(b, i, c);
    }
    for (int i = 1; i <= n; i ++ ) {
        if (dfn[i]) continue;
        getring(i, -1);
        res = 0;
        for (int j = 0; j < ring.size(); j ++ ) dp(ring[j]);
        res = max(res, on_the_ring());
        ans += res;
    }
    printf("%lld\n", ans);
    return 0;
}