30pts 另一种可能

在修改点权时。

减贡献是：先递归，后修改。

加贡献是：先修改，后递归。

原因是靠考虑修改时需要用的是旧值还是值。

大概是像这样，不能把 del() 和 add() 写成一个函数。

CPP

void del(int x) {
    int u = up[top[x]];
    if (!u) return;
    auto cur = query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
    int f0 = cur[0][0], f1 = cur[0][1];
    del(u);
    g[u][0] -= max(f0, f1);
    g[u][1] -= f0;
    cur.n = cur.m = 2;
    cur[0][0] = cur[1][0] = g[u][0];
    cur[0][1] = g[u][1];
    cur[1][1] = -inf;
    update(1, 1, n, dfn[u], cur);
}

void add(int x) {
    int u = up[top[x]];
    if (!u) return;
    auto cur = query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
    int f0 = cur[0][0], f1 = cur[0][1];
    g[u][0] += max(f0, f1);
    g[u][1] += f0;
    cur.n = cur.m = 2;
    cur[0][0] = cur[1][0] = g[u][0];
    cur[0][1] = g[u][1];
    cur[1][1] = -inf;
    update(1, 1, n, dfn[u], cur);
    add(u);
}

讨论操作

回复

相关推荐

30pts 另一种可能