Luogu P4719 【模板】“动态 DP”&动态树分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Mat g[MAXn + 10];
void Update(int x, int v) {
    g[x].a[1][0] -= val[x];
    g[x].a[1][0] += v;
    while (fa[top[x]]) {
        Mat last = query(1, nddfs[top[x]], ed[x]);
        modifyRepPoint(1, nddfs[x], g[x]);
        Mat now = query(1, nddfs[top[x]], ed[x]);
        x = fa[top[x]];
        g[x].a[0][0] -= max(last.a[0][0], last.a[1][0]);
        g[x].a[0][0] += max(now.a[0][0], now.a[1][0]);
        g[x].a[0][1] = g[x].a[0][0];
        g[x].a[1][0] -= last.a[0][0];
        g[x].a[1][0] += now.a[0][0];
    }
    modifyRepPoint(1, nddfs[x], g[x]);
}