BZOJ 2500 幸福的道路：樹形 DP + 單調隊列優化

題目大意

給定一棵帶權樹，定義 a[i] 為從節點 i 出發的最長路徑長度。求 a 數組中最長的連續區間，使得區間內最大值與最小值之差 ≤ m。

解題步驟

1. 樹形 DP 求 a[i]（雙向 DP）

• 第一遍 DFS（自底向上）： 計算 `f[u]` = 從 u 向子樹方向的最長鏈，`g[u]` = 次長鏈（且與最長鏈來自不同子樹）。
• 第二遍 DFS（自頂向下）： 計算 `h[u]` = 從 u 向父節點方向的最長鏈。利用 `f` 和 `g` 避免走回頭路：若最長鏈經過某子節點，則向該子節點傳遞次長鏈或父方向鏈。
• 最終 `a[u] = max(f[u], h[u])`。

2. 單調隊列求最長合法區間

在數組 a[1..n] 上維護兩個單調隊列（單調遞減隊列維護最大值，單調遞增隊列維護最小值）。雙指針滑動窗口，右擴左縮，保證窗口內 `max - min ≤ m`，記錄最大窗口長度。

核心代碼片段 (C++)

// 樹形 DP 部分
void dfs1(int u) {
    for (auto [v, w] : G[u]) {
        dfs1(v);
        long long val = f[v] + w;
        if (val > f[u]) { g[u] = f[u]; f[u] = val; }
        else if (val > g[u]) g[u] = val;
    }
}
void dfs2(int u) {
    a[u] = max(f[u], h[u]);
    for (auto [v, w] : G[u]) {
        long long use = (f[u] == f[v] + w) ? g[u] : f[u];
        use = max(use, h[u]);
        h[v] = use + w;
        dfs2(v);
    }
}

// 單調隊列部分
int qmax[N], qmin[N], hh, tt;
for (int i = 1, j = 1; i <= n; i++) {
    while (hh <= tt && a[qmax[tt]] <= a[i]) tt--;
    qmax[++tt] = i;
    while (hh <= tt && a[qmin[tt]] >= a[i]) tt--;
    qmin[++tt] = i;
    while (a[qmax[hh]] - a[qmin[hh]] > m) {
        if (qmax[hh] == j) hh++;
        if (qmin[hh] == j) hh++;
        j++;
    }
    ans = max(ans, i - j + 1);
}

複雜度

• 樹形 DP：O(N)
• 單調隊列：O(N)
• 總體：O(N)，N ≤ 10^6 可過。