「題解」洛谷 P4074 [WC2013]糖果公園

題目

P4074 [WC2013]糖果公園

簡化題意

給你一棵樹樹，點有點權，帶修改，每一次經過一種點權會有不同的貢獻（随着經過次數再變），問你從一個點到一個點的貢獻和

思路

樹上帶修莫隊。

用 \(cnt[i]\) 表示 \(i\) 這個點的權值的出現次數。

用 \(a[i]\) 表示 \(i\) 号點的權值。

用 \(v[i]\) 表示一權值 \(i\) 的貢獻定值。

用 \(v[i]\) 表示一權值出現 \(i\) 次時的貢獻常數。

加入一個點 \(u\)：

ans += v[++cnt[a[u]]] * w[a[u]]

删掉一個點 \(u\)：

ans -= v[cnt[a[u]]--] * w[a[u]]

先考慮沒有修改，因為加一個點和删一個點都可以 \(O(1)\) 維護，是以莫隊沒問題。

在樹上，樹上莫隊。

如果沒有修改就是一個普通的樹上莫隊。有修改就是樹上帶修莫隊了。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 100001

inline void read(int &T) {
    int x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = !f;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    T = f ? -x : x;
}

void write(long long x) {
    if (x < 0) putchar('-'), write(-x);
    else {
        if (x / 10) write(x / 10);
        putchar(x % 10 + '0');
    }
}

typedef long long ll;
ll ans[MAXN];
int n, m, s, sqrn, pthn, head[MAXN], a[MAXN], v[MAXN], w[MAXN], num[MAXN << 1], cnt[MAXN], vis[MAXN];
int c_, cc, cq, fir[MAXN], la[MAXN], pre[MAXN << 1], dep[MAXN], lg[MAXN], fa[MAXN][21];
struct change {
    int w, pos;
}c[MAXN];
struct query {
    int x, y, t, lca, id;
    friend bool operator < (query q1, query q2) {
        if (num[q1.x] != num[q2.x]) return num[q1.x] < num[q2.x];
        if (num[q1.y] != num[q2.y]) return num[q1.y] < num[q2.y];
        return q1.t < q2.t;
    }
}q[MAXN];
struct Edge {
    int next ,to;
}pth[MAXN << 1];

void add(int from, int to) {
    pth[++pthn].to = to, pth[pthn].next = head[from];
    head[from] = pthn;
}

void dfs(int u, int father) {
    fa[u][0] = father, dep[u] = dep[father] + 1;
    fir[u] = ++c_, pre[c_] = u;
    for (int i = head[u]; i; i = pth[i].next) {
        int x = pth[i].to;
        if (x != father) dfs(x, u);
    }
    la[u] = ++c_, pre[c_] = u;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    while (dep[x] > dep[y]) {
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    }
    if (x == y) return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

void work(int now, ll &ans) {
    if (vis[now]) {
        ans -= 1ll * w[cnt[a[now]]] * v[a[now]];
        --cnt[a[now]];
    }
    else {
        ++cnt[a[now]];
        ans += 1ll * w[cnt[a[now]]] * v[a[now]];
    }
    vis[now] ^= 1;
}

bool okay(int nq, int node) {
    bool flag1 = (fir[node] >= q[nq].x && fir[node] <= q[nq].y && (la[node] < q[nq].x || la[node] > q[nq].y));
    bool flag2 = (la[node] >= q[nq].x && la[node] <= q[nq].y && (fir[node] < q[nq].x || fir[node] > q[nq].y));
    return (flag1 || flag2);
}

int main() {
    read(n), read(m), read(s), sqrn = pow(2 * n, 2.0 / 3.0);
    for (int i = 1; i <= 2 * n; ++i) num[i] = (i - 1) / sqrn + 1;
    for (int i = 1; i <= m; ++i) read(v[i]);
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1, opt, x, y, f; i <= s; ++i) {
        read(opt), read(x), read(y);
        if (opt == 1) {
            f = lca(x, y), q[++cq].id = cq, q[cq].t = cc;
            if (fir[x] > fir[y]) std::swap(x, y);
            if (x == f) {
                q[cq].x = fir[x];
                q[cq].y = fir[y];
            }
            else {
                q[cq].x = la[x];
                q[cq].y = fir[y];
                q[cq].lca = f;
            }
        }
        else c[++cc].w = y, c[cc].pos = x;
    }
    std::sort(q + 1, q + cq + 1);
    int l = 1, r = 0, t = 0;
    ll now = 0;
    for (int i = 1; i <= cq; ++i) {
        while (l > q[i].x) work(pre[--l], now);
        while (r < q[i].y) work(pre[++r], now);
        while (l < q[i].x) work(pre[l++], now);
        while (r > q[i].y) work(pre[r--], now);
        while (t < q[i].t) {
            ++t;
            bool flag = okay(i, c[t].pos);
            if (flag) work(c[t].pos, now);
            std::swap(a[c[t].pos], c[t].w);
            if (flag) work(c[t].pos, now);
        }
        while (t > q[i].t) {
            bool flag = okay(i, c[t].pos);
            if (flag) work(c[t].pos, now);
            std::swap(a[c[t].pos], c[t].w);
            if (flag) work(c[t].pos, now);
            --t;
        }
        if (q[i].lca) work(q[i].lca, now);
        ans[q[i].id] = now;
        if (q[i].lca) work(q[i].lca, now);
    }
    for (int i = 1; i <= cq; ++i) {
        write(ans[i]);
        puts("");
    }
    return 0;
}