yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P4719 【模版】动态DP&动态树分治

发表于 分类于

P4719 【模版】动态DP&动态树分治

题面

题目链接

解法

此处记录一下树剖的写法。

首先有简单的$dp$方程如下：

考虑运用树剖，每次将轻儿子的答案暴力贡献到父亲上面，父亲节点只需要加上重儿子的贡献。

考虑使用矩阵，有这样的转移矩阵：

其中$v$是$u$的重儿子，$g{u,0}$表示轻儿子中不取$u$可以得到的最大贡献，$g{u,1}$表示轻儿子中取$u$可以得到的最大贡献（包括$a_u$）。线段树维护矩阵，修改时暴力跳轻链并修改轻链的父亲，时间复杂度为$O(n\log^2 n)$，看下代码自己敲一下就很容易理解了。

听说拿LCT写可以做到$O(n\log n)$而且跑的飞快？改天有空试试。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/**
 * @file:           P4719.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4719
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Matrix {
    int a[2][2];
    Matrix() { memset(a, -0x3f, sizeof(a)); }
    Matrix operator*(const Matrix& o) const {
        Matrix ret;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    ret.a[i][j] = max(ret.a[i][j], a[i][k] + o.a[k][j]);
        return ret;
    }
} mat[MAXN];
int n, q, a[MAXN];
int f[MAXN][2];
int fa[MAXN], siz[MAXN], wson[MAXN];
int dfn[MAXN], sfa[MAXN], dwn[MAXN], id[MAXN], dfc;
vector<int> g[MAXN];
#define li (i << 1)
#define ri (i << 1 | 1)
#define lson li, l, mid
#define rson ri, mid + 1, r
struct SegmentTree {
    Matrix nd[MAXN * 4];
    void build(int i, int l, int r) {
        if (l == r)
            return void(nd[i] = mat[id[l]]);
        int mid = (l + r) >> 1;
        build(lson), build(rson);
        nd[i] = nd[ri] * nd[li];
    }
    void update(int i, int l, int r, int q) {
        if (l == r)
            return void(nd[i] = mat[id[l]]);
        int mid = (l + r) >> 1;
        if (q <= mid)
            update(lson, q);
        else
            update(rson, q);
        nd[i] = nd[ri] * nd[li];
    }
    Matrix query(int i, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return nd[i];
        int mid = (l + r) >> 1;
        if (qr <= mid)
            return query(lson, ql, qr);
        if (ql > mid)
            return query(rson, ql, qr);
        return query(rson, ql, qr) * query(lson, ql, qr);
    }
} sgt;
void dfs1(int u, int f) {
    fa[u] = f, siz[u] = 1;
    for (auto v : g[u]) {
        if (v == f)
            continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[wson[u]] < siz[v])
            wson[u] = v;
    }
}
void dfs2(int u, int sf) {
    dfn[u] = ++dfc, id[dfc] = u;
    sfa[u] = sf, dwn[u] = u;
    f[u][0] = 0, f[u][1] = a[u];
    mat[u].a[0][0] = 0;
    mat[u].a[0][1] = a[u];
    mat[u].a[1][0] = 0;
    if (wson[u]) {
        dfs2(wson[u], sf);
        dwn[u] = dwn[wson[u]];
        f[u][0] += max(f[wson[u]][0], f[wson[u]][1]);
        f[u][1] += f[wson[u]][0];
    }
    for (auto v : g[u]) {
        if (v == fa[u] || v == wson[u])
            continue;
        dfs2(v, v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
        mat[u].a[0][0] += max(f[v][0], f[v][1]);
        mat[u].a[1][0] += max(f[v][0], f[v][1]);
        mat[u].a[0][1] += f[v][0];
    }
}
void update(int u, int k) {
    mat[u].a[0][1] += k - a[u], a[u] = k;
    while (u) {
        Matrix t1 = sgt.query(1, 1, n, dfn[sfa[u]], dfn[dwn[u]]);
        sgt.update(1, 1, n, dfn[u]);
        Matrix t2 = sgt.query(1, 1, n, dfn[sfa[u]], dfn[dwn[u]]);
        u = fa[sfa[u]];
        mat[u].a[0][0] += max(t2.a[0][0], t2.a[0][1]) - max(t1.a[0][0], t1.a[0][1]);
        mat[u].a[1][0] += max(t2.a[0][0], t2.a[0][1]) - max(t1.a[0][0], t1.a[0][1]);
        mat[u].a[0][1] += t2.a[0][0] - t1.a[0][0];
    }
}
int query(int u) {
    Matrix t = sgt.query(1, 1, n, dfn[sfa[u]], dfn[dwn[u]]);
    return max(t.a[0][0], t.a[0][1]);
}
signed main() {
    read(n), read(q);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    for (int i = 1; i < n; ++i) {
        int u, v;
        read(u), read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    sgt.build(1, 1, n);
    while (q--) {
        int u, k;
        read(u), read(k);
        update(u, k);
        write(query(1)), putchar('\n');
    }
    return 0;
}