Luogu 4719 / 动态DP

Posted on 2019-10-25 Edited on 2022-06-14 Views:

本地笔记整理第一发，比较散，2019/12/8上传

分析

题目要求求取带修改的树上最大独立集，朴素 $\BigO{n^2}$ DP如下：

$\begin{aligned} \dpa[u][0] &= \sum_{v \in \mathrm{ch}(u)} \max\left\{\dpa[v][1], \dpa[v][0]\right\} \\ \dpa[u][1] &= \mathrm{val}[u] + \sum_{v \in \mathrm{ch}(u)} \dpa[v][0] \end{aligned}$

但是这么一次转移是 $\BigO{n}$ 的，考虑优化，定义 $\mathrm{lch}(u)$ 为的轻儿子集合。 $\mathrm{hch}(u)$ 为的重儿子，稍微修改一下，定义

$\begin{aligned} \ldp[u][0] &= \sum_{v \in \lch{u}} \max\left\{\dpa[v][1], \dpa[v][0]\right\} \\ \ldp[u][1] &= \mathrm{val}[u] + \sum_{v \in \lch{u}} \dpa[v][0] \\ \end{aligned}$

则有

$\begin{aligned} \dpa[u][0] &= \max\left\{\dpa[\hch{u}][0],\dpa[\hch{u}][1]\right\} + \ldp[u][0]\\ \dpa[u][1] &= \dpa[\hch{u}][0] + \ldp[u][1] \end{aligned}$

使用Max-Plus Algebra的方式重写：

$\begin{pmatrix} \dpa[u][0] \\ \dpa[u][1] \end{pmatrix} = \begin{pmatrix} \ldp[u][0] & \ldp[u][0] \\ \ldp[u][1] & -\infty \end{pmatrix} \begin{pmatrix} \dpa[\hch{u}][0] \\ \dpa[\hch{u}][1] \end{pmatrix}$

接下来只需要树链剖分维护矩阵转移就行了，单次修改的时间复杂度为 $\BigO{\log^2n}$ 。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010;
const int T = 4 * N;
const int INF = 0x3f3f3f3f;
int n;
int fst[N], nxt[2 * N], to[2 * N], tot = 1;
struct vec {
    int a[2];
    vec() { memset(a, 0, sizeof a); }
    int &operator [](int x) { return a[x]; }
    const int &operator [](int x) const { return a[x]; }
} eye;
struct mat {
    int a[2][2];
    mat() { memset(a, 0, sizeof a); }   
    int *operator [](int x) { return a[x]; }
    const int *operator [](int x) const { return a[x]; }
    mat operator *(const mat &b) const {
        mat c;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = -INF;
                for (int k = 0; k < 2; k++)
                    c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
            }
        }
        return c;
    }
    vec operator *(const vec &b) const {
        vec c;
        for (int i = 0; i < 2; i++) {
            c[i] = -INF;
            for (int j = 0; j < 2; j++)
                c[i] = max(c[i], a[i][j] + b[j]);
        }
        return c;
    }
};
void link(int u, int v) {
    nxt[++tot] = fst[u];
    fst[u] = tot; to[tot] = v;
}
int cnt = 0, id[N], top[N], dep[N], bot[N], sz[N], son[N], fa[N];
int a[N], ldp[N][2], dp[N][2];
mat val[T], init[N];
void dfs1(int u, int p) {
    dep[u] = dep[p] + 1; fa[u] = p;
    sz[u] = 1; int mx = -1;
    for (int e = fst[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == p) continue;
        dfs1(v, u); sz[u] += sz[v];
        if (sz[v] > mx) mx = sz[v], son[u] = v;
    }
}
void dfs2(int u, int tp) {
    id[u] = ++cnt, top[u] = tp;
    bot[top[u]] = u;
    if (son[u]) dfs2(son[u], tp);
    for (int e = fst[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v); 
    }
}
#define lch (rt << 1)
#define rch (lch | 1)
#define larg lch, l, mid
#define rarg rch, mid + 1, r
void pushup(int rt) {
    val[rt] = val[lch] * val[rch];
}
void build(int rt, int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(larg); build(rarg);
    pushup(rt);
}
mat query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return val[rt];
    int mid = (l + r) >> 1;
    if (qr <= mid) return query(larg, ql, qr);
    if (ql > mid) return query(rarg, ql, qr);
    return query(larg, ql, qr) * query(rarg, ql, qr);
}
void update(int rt, int l, int r, int p, const mat &v) {
    if (l == r) { val[rt] = v; return; }
    int mid = (l + r) >> 1;
    if (p <= mid) update(larg, p, v);
    else update(rarg, p, v);
    pushup(rt);
}
void updateu(int u) {
    mat m; m[0][0] = m[0][1] = ldp[u][0];
    m[1][0] = ldp[u][1]; m[1][1] = -INF;
    update(1, 1, n, id[u], m);
}
void dfs3(int u) {
    ldp[u][0] = 0, ldp[u][1] = a[u];
    for (int e = fst[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == fa[u]) continue;
        dfs3(v);
        if (v == son[u]) continue;
        ldp[u][0] += max(dp[v][0], dp[v][1]);
        ldp[u][1] += dp[v][0];
    }
    updateu(u);
    vec res = query(1, 1, n, id[u], id[bot[top[u]]]) * eye;
    dp[u][0] = res[0]; dp[u][1] = res[1];
}
void modify(int u, int p) {
    ldp[u][1] += p - a[u]; a[u] = p;
    updateu(u);
    while (true) {
        u = top[u];
        vec res = query(1, 1, n, id[u], id[bot[u]]) * eye;
        if (u != 1) {
            ldp[fa[u]][0] += max(res[0], res[1]) - max(dp[u][0], dp[u][1]);
            ldp[fa[u]][1] += res[0] - dp[u][0];
        }
        dp[u][0] = res[0]; dp[u][1] = res[1];
        if (u == 1) break;
        updateu(u = fa[u]);
    }
}
int main() {
    int q; scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        link(x, y); link(y, x);
    }
    dfs1(1, 0); dfs2(1, 1); build(1, 1, n); dfs3(1);
    while (q--) {
        int x, y; scanf("%d%d", &x, &y);
        modify(x, y);
        printf("%d\n", max(dp[1][0], dp[1][1]));
    }
    return 0;
}