基于变换合并的树上动态 DP

动态最大独立集

显然有 $dp(u,0/1)$ 表示点 $u$ 是否选,转移显然。

把答案拆成两部分,只选取轻儿子的 $dp$ 值 $g(u,0/1)$ 和本来的 $dp$ 值 $f(u,0/1)$。

对于点 $u$ 的重儿子 $v$,可以列出转移方程:

$$
f(u,0)=g(u,0)+max(f(v,0),f(v,1))=max(g(u, 0)+f(v, 0), g(u,0) + f(v, 1)) \
f(u,1)=g(u,1)+f(v,0)
$$

定义一个广义的矩阵乘法,加法改为取 $\max$,乘法改为加法,则有转移矩阵:
$$
\begin{bmatrix}
g(u,0) & g(u, 0) \
g(u,1) & -\infty
\end{bmatrix}
\begin{bmatrix}
f(v,0) \
f(v,1)
\end{bmatrix}
=
\begin{bmatrix}
f(u,0) \
f(u,1)
\end{bmatrix}
$$
这个 $dp$ 现在可以改成用树链剖分维护每个点只选取轻儿子 $dp$ 值的矩阵。

一个点的 $dp$ 值,可以通过从该点重链的叶子结点往上转移的方式得到。

对于修改操作,一个点所处的重链均不需要修改,只需要修改重链的链头的父亲,记录一下修改前后的链头变化,更新一下这个父亲的矩阵,再通过重链往上爬。

单次操作复杂度:$\mathcal{O}(8\log^2n)$。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

struct Mat {
static const int M = 2;
int a[M][M];
Mat() { for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) a[i][j] = -inf; }
void clear() { ms(a, 0); }
void eye() { for (int i = 0; i < M; i++) a[i][i] = 1; }
int* operator [] (int x) { return a[x]; }
const int* operator [] (int x) const { return a[x]; }
Mat operator * (const Mat& b) {
const Mat& a = *this; Mat r;
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++)
r[i][j] = max(r[i][j], a[i][k] + b[k][j]);
return r;
}
} b[maxn << 2], val[maxn];

int n, q, a[maxn];
vector<int> edge[maxn];

int dep[maxn], siz[maxn], son[maxn], fa[maxn], top[maxn];
void dfs(int u, int f) {
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
int m = -1;
for (int& v: edge[u]) {
if (v == f) continue;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] > m) m = siz[v], son[u] = v;
}
}
int f[maxn][2], g[maxn][2];
int id[maxn], mp[maxn], ed[maxn], tot;
void dfs(int u, int ff, int tp) {
g[u][1] = a[u];
id[u] = ++tot; mp[tot] = u;
top[u] = tp; ed[tp] = tot;
if (!son[u]) {
// ???
f[u][1] = a[u];
return ;
}
dfs(son[u], u, tp);
f[u][0] += max(f[son[u]][0], f[son[u]][1]);
f[u][1] += f[son[u]][0];
for (int& v: edge[u]) {
if (v == ff || v == son[u]) continue;
dfs(v, u, v);
g[u][0] += max(f[v][0], f[v][1]);
g[u][1] += f[v][0];
}
f[u][0] += g[u][0];
f[u][1] += g[u][1];
}

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
void pushup(int rt) {
b[rt] = b[rt << 1] * b[rt << 1 | 1];
}
void build(int l, int r, int rt) {
if (l == r) {
int u = mp[l];
val[u][0][0] = val[u][0][1] = g[u][0];
val[u][1][0] = g[u][1];
val[u][1][1] = -inf;
b[rt] = val[u];
return ;
}
int m = (l + r) / 2;
build(lson); build(rson);
pushup(rt);
}
void update(int i, int l, int r, int rt) {
if (l == r) {
b[rt] = val[mp[l]]; return ;
}
int m = (l + r) / 2;
if (i <= m) update(i, lson);
else update(i, rson);
pushup(rt);
}
Mat query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return b[rt];
int m = (l + r) / 2;
if (R <= m) return query(L, R, lson);
if (L > m) return query(L, R, rson);
return query(L, R, lson) * query(L, R, rson);
}

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 2, u, v; i <= n; i++) {
scanf("%d%d", &u, &v);
edge[u].push_back(v); edge[v].push_back(u);
}
dfs(1, 0); dfs(1, 0, 1); build(1, n, 1);
int x, y;
while (q--) {
scanf("%d%d", &x, &y);
val[x][1][0] += y - a[x]; a[x] = y;
while (x) {
int tp = top[x];
Mat last = query(id[tp], ed[tp], 1, n, 1);
update(id[x], 1, n, 1);
Mat nw = query(id[tp], ed[tp], 1, n, 1);
x = fa[tp];
val[x][0][0] += max(nw[0][0], nw[1][0]) - max(last[0][0], last[1][0]);
val[x][0][1] = val[x][0][0];
val[x][1][0] += nw[0][0] - last[0][0];
}
Mat ans = query(id[1], ed[1], 1, n, 1);
printf("%d\n", max(ans[0][0], ans[1][0]));
}
return 0;
}
  • 本文作者: XLor
  • 本文链接: https://xlor.cn/2019/6/ddp/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!