您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 3052 糖果公園：帶修改樹上莫隊算法完整解析

編輯：關於C++

題目大意

給定一棵 $n$ 節點的樹，每個節點有顏色 $c_i$。支持兩種操作：

查詢：路徑 $u \to v$ 上顏色權值和，權值 $w_k$ 為顏色出現次數 $k$ 時的貢獻。
修改：單點修改節點顏色。

離線處理所有操作，輸出每次查詢答案。$n, m \le 10^5$，時限 200s、記憶體 512MB。

核心算法：帶修改的樹上莫隊

將樹上路徑查詢轉化為序列區間查詢，結合「時間維度」處理修改操作。

1. 樹上路徑 → 序列區間（DFS 序 + LCA）

對樹進行 DFS，記錄進入時間 dfn[u]、退出時間、深度 dep[u]、2^k 祖先 fa[u][k]。
路徑 $u \to v$ 分兩種情況：


int lca = LCA(u, v);
if (lca == u) {
    // u 是 v 祖先：區間 [dfn[u], dfn[v]]
    query.l = dfn[u]; query.r = dfn[v]; query.lca = 0;
} else {
    // 否則：區間 [dfn[u], dfn[v]] + 額外加上 lca
    if (dfn[u] > dfn[v]) swap(u, v);
    query.l = dfn[u]; query.r = dfn[v]; query.lca = lca;
}

區間內節點出現奇數次即在路徑上（利用 DFS 序進出各一次的性質），lca 需額外處理。

2. 莫隊排序：三維關鍵字

將查詢按 (block(l), block(r), time) 排序：

塊大小 $B = n^{2/3}$，平衡三維移動代價。
同塊內 $r$ 升序，$r$ 塊相同時 $time$ 升序（或奇偶塊 $r$ 反向優化）。


int B = pow(n, 2.0/3);
bool cmp(Query a, Query b) {
    int block_a = a.l / B, block_b = b.l / B;
    if (block_a != block_b) return block_a < block_b;
    int block_ra = a.r / B, block_rb = b.r / B;
    if (block_ra != block_rb) return block_ra < block_rb;
    return a.time < b.time;
}

3. 四個指針移動：`add`/`del`/`apply_mod`/`revert_mod`

區間擴縮：移動 L、R 指針，翻轉節點「在路徑中」狀態（vis[u] ^= 1），維護顏色計數 cnt[color] 與答案 ans。
時間前進/後退：應用/撤銷修改操作。若被修改節點當前在路徑中，需先 del、改顏色、再 add；否則直接改顏色。


void toggle(int u) { // 節點進出路徑
    int c = color[u];
    if (vis[u]) { // 移出
        ans -= V[c] * w[cnt[c]--];
    } else {      // 移入
        ans += V[c] * w[++cnt[c]];
    }
    vis[u] ^= 1;
}

void applyMod(int idx) { // 應用第 idx 個修改
    Mod& m = mods[idx];
    if (vis[m.pos]) { toggle(m.pos); color[m.pos] = m.new_c; toggle(m.pos); }
    else color[m.pos] = m.new_c;
}
void revertMod(int idx) { // 撤銷第 idx 個修改
    Mod& m = mods[idx];
    if (vis[m.pos]) { toggle(m.pos); color[m.pos] = m.old_c; toggle(m.pos); }
    else color[m.pos] = m.old_c;
}

4. 答案計算

維護 cnt[color] = 顏色在當前路徑中出現次數，ans += V[c] * w[cnt[c]]。$V[c]$ 為顏色基礎值，$w[k]$ 為第 $k$ 次出現的權重。

完整代碼框架


#include 
using namespace std;
const int N = 100005;
struct Query { int l, r, lca, time, id; };
struct Mod { int pos, old_c, new_c; };

int n, m, k, B, timer;
int color[N], dfn[N], rev[N], dep[N], fa[N][17];
bool vis[N];
int cnt[N];
long long V[N], w[N], ans, res[N];
vector g[N];
Query qs[N]; Mod ms[N];

// DFS, LCA, 莫隊排序, toggle, applyMod, revertMod, 主流程
// 見上文關鍵函數

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i=1;i<=m;++i) cin >> V[i];
    for (int i=1;i<=n;++i) cin >> w[i];
    for (int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); }
    
    // DFS 預處理 dfn, dep, fa
    // 讀取操作，分離查詢與修改，構建 Query 與 Mod 數組
    // 排序查詢
    // 莫隊主循環移動 L/R/time
    // 輸出答案
}