BZOJ 1023 仙人掌圖直徑：樹上 DP + 單調隊列優化

題目描述

求一個仙人掌圖的直徑。仙人掌圖特性：每條邊要么是割邊（橋），要么屬於唯一一個簡單環。

解題思路

利用深度優先搜尋（DFS）辨識橋與環，結合動態規劃計算直徑。

狀態定義

f[u] 表示以 u 為根的子樹中最長鏈長度。

轉移方程

• 橋邊 (u, v)：
  ans = max(ans, f[u] + f[v] + 1)
f[u] = max(f[u], f[v] + 1)
• 環邊：將環拆成鏈，複製一遍形成長度 2×cnt 的陣列，使用單調隊列在 O(cnt) 內求出環上的最大直徑貢獻，再用環上節點的 f 值更新根節點的 f[u]。

核心程式碼

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = N << 1;
int ans, ind, tot, cnt, fa[N], cir[N << 1];
int to[M << 1], nxt[M << 1], head[N];
int dfn[N], low[N], f[N];

struct data { int p, w; } q[N];

void add(int u, int v) {
    to[tot] = v, nxt[tot] = head[u], head[u] = tot++;
    to[tot] = u, nxt[tot] = head[v], head[v] = tot++;
}

void gao() { // 單調隊列處理環
    int h = 1, r = 1;
    for (int i = 1; i <= cnt; ++i) cir[cnt + i] = cir[i];
    for (int i = 1; i <= (cnt << 1); ++i) {
        while (h < r && i - q[h].p > cnt / 2) ++h;
        while (h < r && q[r].w <= f[cir[i]] - i) --r;
        q[++r].p = i, q[r].w = f[cir[i]] - i;
        ans = max(ans, f[cir[i]] + i + q[h].w);
    }
}

void dfs(int u) {
    low[u] = dfn[u] = ++ind;
    for (int i = head[u], v; ~i; i = nxt[i]) {
        v = to[i];
        if (fa[v] && v != fa[u]) low[u] = min(low[u], dfn[v]);
        if (!fa[v]) {
            fa[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
    }
    for (int i = head[u], v; ~i; i = nxt[i]) {
        v = to[i];
        if (fa[v] == u && low[v] > dfn[u]) { // 橋
            ans = max(ans, f[u] + f[v] + 1);
            f[u] = max(f[u], f[v] + 1);
        }
        if (fa[v] != u && dfn[u] < dfn[v]) { // 環
            cnt = 0;
            while (v != fa[u]) cir[++cnt] = v, v = fa[v];
            gao();
            for (int j = 1; j < cnt; ++j)
                f[u] = max(f[u], f[cir[j]] + min(j, cnt - j));
        }
    }
}

int main() {
    int n, m;
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y, z; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        for (int j = 1; j < x; ++j) {
            scanf("%d", &z);
            add(y, z);
            y = z;
        }
    }
    fa[1] = -1;
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

複雜度

• 時間：O(N + M)，單調隊列保證環處理線性。
• 空間：O(N + M)

此題展示了仙人掌圖結構特性如何轉化為樹上 DP，並以單調隊列優化環上最長路徑計算。