糖果公园题解

题目大意

给定一棵 $n$ 个节点的树，每个节点有一种糖果 $C_i$ (共 m 种)。每种糖果有美味值 $V_i$ ，品尝第 $k$ 次同种糖果的新奇感为 $W_k$ 。游客从 $u$ 走到 $v$ 的愉悦度为路径上所有节点 $i$ 的 $V_{C_i}$ × $W_{count(C_i)}$ 之和，其中

count(C_i)

是此种糖果在当前路径上出现的次数。

需要支持两种操作：

修改某个节点的糖果种类。
查询某条路径的愉悦度。

算法分析

一看就指了解这题是 树上带修改莫队 问题。与序列莫队不同，本解法采用 DFN序结合路径移动的方式，直接处理树上路径。
核心思路：DFN序结合带修莫队
DFN序预处理：通过DFS得到每个节点的DFN序（深度优先搜索序），用于莫队的块划分。
路径移动：使用 work 函数通过不断移动到父节点来改变当前路径。对于路径 $(u, v)$ ，通过移动端点到LCA来添加或移除节点。
处理修改：增加时间维度 $t$ ，记录修改操作。在莫队移动左右指针时，同时移动时间指针来处理修改。
LCA处理：关键点在于，路径移动后，LCA节点可能未被包含，因此需要在计算答案前临时添加LCA点，计算后移除。
块大小设置：通常取 $B = n^{2/3}$ ，总时间复杂度为 $O(n^{5/3})$ 。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200005;
int n, M, m, dfn[N], idx, vv[N], ww[N], b[N], a[N], lg[N], f[N][20], d[N], res, ans[N];
int B = 200;
bitset<N>ex;
struct node{
    int l, r, id, t;
}q[N], qr[N];
vector<int>v[N];
bool operator < (node x, node y) {
    int bx = dfn[x.l] / B, by = dfn[y.l] / B;
    if (bx != by) return bx < by;
    int cx = dfn[x.r] / B, cy = dfn[y.r] / B;
    if (cx != cy) return cx < cy;
    return x.t < y.t;
}
void dfs(int x, int fa) {
    dfn[x] = ++idx;
    d[x] = d[fa] + 1;
    f[x][0] = fa;
    for (auto to : v[x]) {
        if (to != fa) {
            dfs(to, x);
        }
    }

}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    int diff = d[x] - d[y];
    for (int i = 0; diff; ++i) {
        if (diff & 1) x = f[x][i];
        diff >>= 1;
    }
    if (x == y) return x;
    for (int i = lg[n]; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void add(int x) {
    b[a[x]]++;
    res += vv[a[x]] * ww[b[a[x]]];
}
void del(int x) {
    res -= vv[a[x]] * ww[b[a[x]]];
    b[a[x]]--;
}
void work(int x, int t) {
    int l = lca(x, t);
    while (x != l) {
        if (ex[x]) {
            ex[x] = 0;
            del(x);
        } else {
            ex[x] = 1;
            add(x);
        }
        x = f[x][0];
    }
    x = t;
    while (x != l) {
        if (ex[x]) {
            ex[x] = 0;
            del(x);
        } else {
            ex[x] = 1;
            add(x);
        }
        x = f[x][0];
    }
}
void change(int x, int y) {
    if (ex[x]) {
        del(x);
        a[x] = y;
        add(x);
    } else {
        a[x] = y;
    }
}
signed main() {
    cin >> n >> M >> m;
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= M; i++) cin >> vv[i];
    for (int i = 1; i <= n; i++) cin >> ww[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];

    idx = 0;
    dfs(1, 0);
    for (int i = 1; i <= lg[n]; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }

    int qcnt = 0, tcnt = 0;
    if(pow((double)n, 2.0/3.0) > 1){
        B = pow((double)n, 2.0/3.0);
    }
    else{
        B = 1;
    }
    for (int i = 1; i <= m; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 0) {
            tcnt++;
            qr[tcnt].l = x;
            qr[tcnt].r = a[x];
            qr[tcnt].id = y;
            qr[tcnt].t = tcnt;
            a[x] = y;
        } else {
            qcnt++;
            q[qcnt].l = x;
            q[qcnt].r = y;
            q[qcnt].id = qcnt;
            q[qcnt].t = tcnt;
        }
    }

    for (int i = tcnt; i >= 1; --i) {
        a[ qr[i].l ] = qr[i].r;
    }

    sort(q + 1, q + qcnt + 1);

    int l = 1, r = 1, t = 0;
    for (int i = 1; i <= n; i++) ex[i] = 0;
    for (int i = 1; i <= M; i++) b[i] = 0;
    res = 0;

    for (int i = 1; i <= qcnt; i++) {
        work(l, q[i].l);
        l = q[i].l;
        work(r, q[i].r);
        r = q[i].r;
        while (t < q[i].t) {
            t++;
            change(qr[t].l, qr[t].id);
        }
        while (t > q[i].t) {
            change(qr[t].l, qr[t].r);
            t--;
        }
        int lc = lca(l, r);
        add(lc); // 临时添加LCA点
        ans[q[i].id] = res;
        del(lc); // 移除LCA点以恢复状态
    }
    for (int i = 1; i <= qcnt; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

糖果公园 - 题解

糖果公园 题解

题目大意

算法分析

CODE

糖果公园题解