抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

前言

动态 dp 一般用来解决树上的 dp 问题,同时需要支持修改点权/边权的操作。

前置知识:矩阵乘法,树链剖分

模板题

题意

洛谷 P4719 【模板】动态 DP

带修改点权的树上最大独立集, n 点, m 次操作

不带修改操作

没有上司的舞会嘛不就是。令 f_{i,0} 表示 i 子树内不选 i 点所构成的最大独立集点权之和, f_{i, 1} 表示 i 子树选 i 点构成的最大独立集点权之和。则易得转移:

\begin{cases} f_{u, 0} = \sum_{v\in\operatorname{son}(u)} \max\{f_{v, 0}, f_{v, 1}\}\\ f_{u, 1} = \operatorname{val}_u + \sum_{v\in\operatorname{son}(u) f_{v, 0}} \end{cases}

答案即为 \max\{f_{\mathrm{root}, 0}, f_{\mathrm{root}, 1}\} 。这是普及组的内容。

朴素的暴力

我们注意到,如果带上了修改点权的操作,则只会有从根到该节点的一条链上会产生 dp 值的变化。这是相当重要的一个思考过程。这样的暴力的时间复杂度为 O(nm) (最坏情况下一次操作 O(n)

思考一下这个过程:对链进行操作,无非就是树剖。所以我们考虑使用树链剖分解决这个问题。

树链剖分

树剖的原理是使用线段树或者其他的数据结构来维护一条重链。故其维护的信息必须满足结合律。什么是结合律呢?加法显然就是满足结合律的:

(A + B) + C = A + (B + C)

然而这个 dp 值一看就不是很好维护出什么结合律的样子。。。

怎么办?矩阵。矩阵乘法是满足结合律的。所以我们来看看如何利用矩阵来解决这个问题。

矩阵乘法

首先对这个 dp 式子进行一下修改。由于每次都要对所有儿子求个和太慢了,所以定义一个 g_{i, 0/1} 来简化 dp 的式子。具体地, g_{i, 0} 表示不选 i 且只可以选 i 的轻儿子所在子树的答案, g_{i, 1} 表示选 i 的最大答案。令 x 表示 u 点的重儿子,则

\begin{cases} f_{u, 0} = g_{u, 0} + \max\{f_{x, 0}, f_{x, 1}\}\\ f_{u, 1} = g_{u, 1} + f_{x, 0} \end{cases}

统一一下形式,则

\begin{cases} f_{u, 0} = \max\{g_{u, 0} + f_{x, 0}, g_{u, 0} + f_{x, 1}\}\\ f_{u, 1} = \max\{g_{u, 1} + f_{x, 0}, g_{u, 1} -\infty \} \end{cases}

如是,我们可构造矩阵 \begin{bmatrix}f_{u, 0}\\ f_{u, 1}\end{bmatrix} 。然后定义广义矩阵乘法,使得

\begin{bmatrix} g_{u, 0} & g_{u, 0}\\ g_{u, 1} & -\infty \end{bmatrix} \otimes \begin{bmatrix} f_{x, 0}\\ f_{x, 1} \end{bmatrix} = \begin{bmatrix} f_{u, 0}\\ f_{u, 1} \end{bmatrix}

这里的广义矩阵乘法实际就是

C_{i, j} = \max_{k = 1}^n(A_{i,k} + B_{k, j})

不难发现这样的矩阵乘法也是满足结合律的。

于是我们的矩阵乘法就定义好了。这里将矩阵封装起来就是下面这个样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<int row, int col>
struct Matrix
{
int ele[row][col];
Matrix(int _r = 0, int _c = 0) : r(_r), c(_c) {}
};

template<int m, int n, int p> Matrix<m, p> operator*(Matrix<m, n> m1, Matrix<n, p> m2)
{
Matrix<m, p> ret;
#define RET ret.ele
#define M1 m1.ele
#define M2 m2.ele
memset(ret.ele, 0xcf, sizeof ret.ele);
FOR(i, 0, m - 1)
FOR(k, 0, n - 1)
FOR(j, 0, p - 1)
RET[i][j] = max(RET[i][j], M1[i][k] + M2[k][j]);
return ret;
#undef RET
#undef m1
#undef m2
}

注意到这样子的单位矩阵应为

\begin{bmatrix} 0 & -\infty\\ -\infty & 0 \end{bmatrix}

查询节点的 dp 值

现在回顾一下处理流程。

假设现在要求出 x 节点的 dp 值,怎么办呢?

明确一点:每个节点的 f 值根本就不重要,完全可以现算现用。我们需要记录的是每个节点的转移矩阵,并用线段树维护转移矩阵的乘积。

于是乎,只需要知道 x 所在重链的底部叶子节点 \operatorname{end}(x) 的编号,然后获取 f_{\operatorname{end}(x)} = \begin{bmatrix}0\\ \operatorname{val}_{\operatorname{end}(x)}\end{bmatrix} ,然后连乘上转移矩阵到 x 处就可以了。也就是 query(dfn[x], dfn[end[x]]) * Matrix 就可以了。

修改点权

首先对于转移矩阵,只需要把含 g_{u, 1} 的地方加上 \Delta\mathrm{val}_u 就可以了。

但是,这样一来,祖先的 dp 值就会发生改变,而对于 u 的链顶节点,其一定为另一节点的轻儿子,所以 fa[top[u]] g 值是会发生变化的。

fa[top[u]] g 值由链顶节点的 f 值产生,所以就需要查询出链顶的 f 值。

但这样一来,就又需要一条条链往上的一直修改了。。。

总结一下流程吧:

  1. 把矩阵 \begin{bmatrix}g_{u, 0} & g_{u, 0}\\ g_{u, 1} & -\infty\end{bmatrix} 的左下角加上 \Delta\mathrm{val}_u ,记录到矩阵 T 中。
  2. 在修改之前,查询一个 F = \begin{bmatrix}f_{\operatorname{top}(u), 0}\\f_{\operatorname{top}(u), 1}\end{bmatrix}
  3. 线段树上修改 u 节点的矩阵为 T ,然后查询 F' = \begin{bmatrix}f_{\operatorname{top}(u), 0}\\f_{\operatorname{top}(u), 1}\end{bmatrix}
  4. u\leftarrow \mathrm{fa}(\mathrm{top}(u)) ,若 u = 0 ,结束流程
  5. u 的矩阵第一行减去 \max\{F\} 加上 \max\{F'\} ,左下角减去 F f_{\mathrm{top}(u), 1} 加上 F' f_{\mathrm{top}(u), 1}
  6. 回到第二步

具体实现

遇到的坑点:

  • 线段树的查询函数可能会遇到查询 [0, 0] 的情况,故需要在线段树结构体中记录下一个节点对应的区间,避免死循环。
  • 单位矩阵的初始化不要弄错或者忘记。

代码还是相当长的,内含注释。

注意,这段代码里面使用了重载了 operator() 运算符来访问矩阵内部元素的封装,请在自己编写时老老实实写宏定义或者不要偷懒。这种写法在不开 -O2 的情况下常数极大。

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])

const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;

int head[maxn], to[maxn << 1], nxt[maxn << 1], cnte;

il void add(int u, int v)
{
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

il int max(int a, int b) {return a > b ? a : b;}

template<int row, int col>
struct Matrix
{
int ele[row][col];
il int &operator()(int a, int b) {return ele[a][b];}
};

template<int m, int n, int p> Matrix<m, p> operator*(Matrix<m, n> m1, Matrix<n, p> m2)
{
Matrix<m, p> ret;
memset(ret.ele, 0xcf, sizeof ret.ele);
FOR(i, 0, m - 1)
FOR(k, 0, n - 1)
FOR(j, 0, p - 1)
ret(i, j) = max(ret(i, j), m1(i, k) + m2(k, j));
return ret;
}

Matrix<2, 2> ID, g[maxn];

int n, m, val[maxn];

int fa[maxn], dep[maxn], size[maxn], son[maxn];

void dfs1(int u, int f)
{
fa[u] = f, size[u] = 1, dep[u] = dep[f] + 1;
GO(u)
{
if (v == f) continue;
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]]) son[u] = v;
}
return;
}

//正常的树剖dfs1

int dfnClock, dfn[maxn], nfd[maxn], top[maxn], end[maxn];
int f[maxn][2];

void dfs2(int u, int topf)
{
top[u] = topf, dfn[u] = ++dfnClock, nfd[dfnClock] = u;//记录nfd是方便下面的线段树操作
if (!son[u])//叶子节点
{
f[u][1] = val[u];//f值很容易得到
g[u] = ID;//g矩阵赋为单位矩阵
end[u] = u;//记录链底部
return;
}
g[u](1, 0) = val[u], g[u](1, 1) = -INF;//初始化g矩阵
dfs2(son[u], topf);
end[u] = end[son[u]];//更新链底
GO(u)
{
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
g[u](0, 0) = g[u](0, 1) += max(f[v][0], f[v][1]);//更新g
g[u](1, 0) += f[v][0];//更新g
}
f[u][0] = g[u](0, 0) + max(f[son[u]][0], f[son[u]][1]);//利用g更新f,以计算父亲的g和f
f[u][1] = g[u](1, 0) + f[son[u]][0];
return;
}

struct node
{
int l, r;//不记录l和r的话对于查询区间为[0,0] 的情况会死循环
Matrix<2, 2> val;
} tree[maxn << 2];

#define L (k << 1)
#define R (L | 1)
#define M ((i + j) >> 1)

il void pushup(int k)
{
tree[k].val = tree[L].val * tree[R].val;
return;
}

void build(int i, int j, int k)
{
tree[k].l = i, tree[k].r = j;
if (i == j)
{
tree[k].val = g[nfd[i]];//此处即为nfd的作用
return;
}
build(i, M, L);
build(M + 1, j, R);
pushup(k);
return;
}

Matrix<2, 2> query(int k, int x, int y)//查询操作,查询[x, y] 的矩阵连乘积
{
int i = tree[k].l, j = tree[k].r;
if (x <= i && y >= j) return tree[k].val;
Matrix<2, 2> ret = ID;
if (x <= M) ret = query(L, x, y);
if (y > M) ret = ret * query(R, x, y);//注意乘的先后
return ret;
}

void modify(int k, int x, int p)//把线段树 x 点上的值赋为 p 的矩阵
{
int i = tree[k].l, j = tree[k].r;
if (i == j)
{
tree[k].val = g[p];
return;
}
if (x <= M) modify(L, x, p);
else modify(R, x, p);
pushup(k);
return;
}

Matrix<2, 1> query(int x)//查询 x 点的 dp 值
{
Matrix<2, 1> tmp;
tmp(0, 0) = 0, tmp(1, 0) = val[end[x]];//最右边,初始化
return query(1, dfn[x], dfn[end[x]]) * tmp;//连乘给上去
}

void modify(int x, int y)//将 x 的点权修改为 y
{
Matrix<2, 1> F0, F1;
g[x](1, 0) += y - val[x];
F0 = query(top[x]);
val[x] = y;
while (x)
{
modify(1, dfn[x], x);//把线段树上修改了
F1 = query(top[x]);
x = fa[top[x]];
g[x](0, 0) = g[x](0, 1) += max(F1(0, 0), F1(1, 0)) - max(F0(0, 0), F0(1, 0));
g[x](1, 0) += F1(0, 0) - F0(0, 0);
F0 = query(top[x]);
}
return;
}

int main()
{
ID(1, 0) = ID(0, 1) = -INF;//单位矩阵
n = read(), m = read();
FOR(i, 1, n) val[i] = read();
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, n, 1);
while (m--)
{
int x = read(), y = read();
modify(x, y);
Matrix<2, 1> ans = query(1);
printf("%d\n", max(ans(0, 0), ans(0, 1)));
}
return 0;
}

序列上的动态 dp

题意

SPOJ GSS3

n 个数, m 次操作, n,m\le 50000 。每次操作要么修改 A_x y ,要么询问 [l,r] 的最大连续子段和。 |A_i|\le 10000

其他的解法

使用线段树来记录区间和,区间最大子段和,区间最大前/后缀和,然后直接做。

其实这确实是一道线段树的好题,可以和 GSS1 一起食用。

这里不考虑这些做法。

从 dp 方程说起

众所周知,我们可以这样定义 dp 的状态:设 f_i 为以 i 结尾的最大子段和, g_i [1,i] 的最大子段和,则方程易得:

\begin{cases} f_i = \max\{f_{i - 1} + a_i, a_i\}\\ g_i = \max\{f_i, g_{i - 1}\} \end{cases}

然后我们尝试构造一下矩阵 \begin{bmatrix}f_i\\g_i\end{bmatrix} ,但是发现转移写不出来,故加一行: \begin{bmatrix}f_i\\g_i\\0\end{bmatrix} 则转移就有了:

\begin{bmatrix} a_i & -\infty & a_i\\ a_i & 0 & a_i\\ -\infty & -\infty & 0 & \end{bmatrix} \otimes \begin{bmatrix} f_{i - 1}\\ g_{i - 1}\\ 0 \end{bmatrix} = \begin{bmatrix} f_{i}\\ g_i\\ 0 \end{bmatrix}

这里的 \otimes 和上文是一样的,都表示 C_{i,j} = \max_{k = 1}^n\{A_{i, k} + B_{k, j}\} 。具体的构造其实不难,自己手玩一下就可以构造出来。

于是我们就用线段树来维护转移矩阵 \begin{bmatrix}a_i & -\infty & a_i\\a_i & 0 & a_i\\-\infty & -\infty & 0 &\end{bmatrix} 的连乘积(但是一定要注意是从右往左乘),每次修改操作就修改矩阵就可以了。查询操作就初始化一下 ,最右边的矩阵肯定是 \begin{bmatrix}a_l\\a_l\\0\end{bmatrix} ,查询出 [l + 1, r] 的连乘积再左乘给初始矩阵就得解了。

单位矩阵易构造为

\begin{bmatrix} 0 & -\infty & -\infty\\ -\infty & 0 & -\infty\\ -\infty & -\infty & 0 \end{bmatrix}

实现

注意,这段代码里面使用了重载了 operator() 运算符来访问矩阵内部元素的封装,请在自己编写时老老实实写宏定义或者不要偷懒。这种写法在不开 -O2 的情况下常数极大。

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
#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int max(int a, int b) {return a > b ? a : b;}

template<int row, int col>
struct Matrix
{
int ele[row][col];
Matrix() {}
int &operator()(int a, int b) {return ele[a][b];}
};

template<int m, int n, int p> Matrix<m, p> operator*(Matrix<m, n> m1, Matrix<n, p> m2)
{
Matrix<m, p> ret;
memset(ret.ele, 0xcf, sizeof ret.ele);
FOR(i, 0, m - 1)
FOR(k, 0, n - 1)
FOR(j, 0, p - 1)
ret(i, j) = max(ret(i, j), m1(i, k) + m2(k, j));
return ret;
}

struct node
{
int l, r;
Matrix<3, 3> val;
} tree[maxn << 2];

int n, a[maxn];
Matrix<3, 3> ID;

#define L (k << 1)
#define R (L | 1)
#define M ((i + j) >> 1)

void pushup(int k)
{
tree[k].val = tree[R].val * tree[L].val;
return;
}

Matrix<3, 3> makeMat(int x)
{
Matrix<3, 3> ret;
ret(0, 0) = ret(0, 2) = ret(1, 0) = ret(1, 2) = x;
ret(0, 1) = ret(2, 0) = ret(2, 1) = -INF;
ret(1, 1) = ret(2, 2) = 0;
return ret;
}

void build(int i, int j, int k)
{
tree[k].l = i, tree[k].r = j;
if (i == j)
{
tree[k].val = makeMat(a[i] = read());
return;
}
build(i, M, L);
build(M + 1, j, R);
pushup(k);
return;
}

Matrix<3, 3> query(int k, int x, int y)
{
if (x > y) return ID;
int i = tree[k].l, j = tree[k].r;
if (x <= i && y >= j) return tree[k].val;
Matrix<3, 3> ret = ID;
if (x <= M) ret = query(L, x, y);
if (y > M) ret = query(R, x, y) * ret;
return ret;
}

void modify(int k, int x, int z)
{
int i = tree[k].l, j = tree[k].r;
if (i == j)
{
tree[k].val = makeMat(a[i] = z);
return;
}
if (x <= M) modify(L, x, z);
else modify(R, x, z);
pushup(k);
return;
}

int main()
{
ID(0, 1) = ID(0, 2) = ID(1, 0) = ID(1, 2) = ID(2, 0) = ID(2, 1) = -INF;
n = read();
build(1, n, 1);
int q = read();
while (q--)
{
int op = read(), x = read(), y = read();
if (!op) modify(1, x, y);
else
{
Matrix<3, 1> ret;
ret(0, 0) = ret(1, 0) = a[x], ret(2, 0) = 0;
ret = query(1, x + 1, y) * ret;
printf("%d\n", ret(1, 0));
}
}
return 0;
}

当然也有另一种实现,就是只获取所有矩阵的连乘积,然后取 (1, 2) 位置上的元素,不难发现 (1, 2) 上的元素就是 g 。实际上都可以 AC。

NOIP2018 D2T3 保卫王国

题意

题面。给定一棵有点权的树,每次操作选定两个点强制选或不选,问这次操作下整棵树的最小点覆盖。

动态 DP 的思路

总点权 = 最大独立集 + 最小点覆盖。直接用求最大独立集的方法做就行了。

强制选一个点即为这个点不能在最大独立集中出现,将点权设为 -\infty 即可。

强制不选某个点即为这个点必须在最大独立集中出现,将点权设为 +\infty 并让总点权也加上 +\infty 即可。

剩下的就是注意常数了。

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])

const int maxn = 1e5 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

int head[maxn], to[maxn << 1], nxt[maxn << 1], cnte;

il void add(int u, int v)
{
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

typedef long long ll;

const ll INF = 1e15;

il ll max(ll a, ll b) {return a > b ? a : b;}

template<int row, int col>
struct Matrix
{
ll ele[row][col];
Matrix() {}
};

template<int m, int n, int p> Matrix<m, p> operator*(Matrix<m, n> m1, Matrix<n, p> m2)
{
Matrix<m, p> ret;
#define RET ret.ele
#define M1 m1.ele
#define M2 m2.ele
memset(ret.ele, 0xcf, sizeof ret.ele);
FOR(i, 0, m - 1)
FOR(k, 0, n - 1)
FOR(j, 0, p - 1)
RET[i][j] = max(RET[i][j], M1[i][k] + M2[k][j]);
return ret;
#undef RET
#undef m1
#undef m2
}

Matrix<2, 2> ID, g[maxn];

int n, m;
ll p[maxn], sump;

int dep[maxn], fa[maxn], size[maxn], son[maxn];

void dfs1(int u, int f)
{
dep[u] = dep[f] + 1, fa[u] = f, size[u] = 1;
GO(u)
{
if (v == f) continue;
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]]) son[u] = v;
}
return;
}

int top[maxn], end[maxn], dfn[maxn], nfd[maxn], dfnClock;
ll f[maxn][2];

void dfs2(int u, int topf)
{
top[u] = topf, dfn[u] = ++dfnClock, nfd[dfnClock] = u;//记录nfd是方便下面的线段树操作
if (!son[u])//叶子节点
{
f[u][1] = p[u];//f值很容易得到
g[u] = ID;//g矩阵赋为单位矩阵
end[u] = u;//记录链底部
return;
}
#define G g[u].ele
G[1][0] = p[u], G[1][1] = -INF;//初始化g矩阵
dfs2(son[u], topf);
end[u] = end[son[u]];//更新链底
GO(u)
{
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
G[0][0] = G[0][1] += max(f[v][0], f[v][1]);//更新g
G[1][0] += f[v][0];//更新g
}
f[u][0] = G[0][0] + max(f[son[u]][0], f[son[u]][1]);//利用g更新f,以计算父亲的g和f
f[u][1] = G[1][0] + f[son[u]][0];
return;
#undef G
}

struct node
{
int l, r;
Matrix<2, 2> val;
} tree[maxn << 2];

#define L (k << 1)
#define R (L | 1)
#define M ((i + j) >> 1)

il void pushup(int k)
{
tree[k].val = tree[L].val * tree[R].val;
return;
}

void build(int i, int j, int k)
{
tree[k].l = i, tree[k].r = j;
if (i == j)
{
tree[k].val = g[nfd[i]];
return;
}
build(i, M, L);
build(M + 1, j, R);
pushup(k);
return;
}

Matrix<2, 2> query(int k, int x, int y)
{
int i = tree[k].l, j = tree[k].r;
if (x <= i && y >= j) return tree[k].val;
Matrix<2, 2> ret = ID;
if (x <= M) ret = query(L, x, y);
if (y > M) ret = ret * query(R, x, y);
return ret;
}

void modify(int k, int x, int p)
{
int i = tree[k].l, j = tree[k].r;
if (i == j)
{
tree[k].val = g[p];
return;
}
if (x <= M) modify(L, x, p);
else modify(R, x, p);
pushup(k);
return;
}

Matrix<2, 1> query(int x)
{
Matrix<2, 1> ret;
#define RET ret.ele
RET[0][0] = 0, RET[1][0] = p[end[x]];
return query(1, dfn[x], dfn[end[x]]) * ret;
#undef RET
}

void modify(int x, ll y)
{
Matrix<2, 1> f0, f1;
#define G g[x].ele
#define F0 f0.ele
#define F1 f1.ele
G[1][0] += y - p[x];
f0 = query(top[x]);
p[x] = y;
while (x)
{
modify(1, dfn[x], x);
f1 = query(top[x]);
x = fa[top[x]];
G[0][0] = G[0][1] += max(F1[0][0], F1[1][0]) - max(F0[0][0], F0[1][0]);
G[1][0] += F1[0][0] - F0[0][0];
f0 = query(top[x]);
}
return;
#undef G
#undef F0
#undef F1
}

int main()
{
ID.ele[1][0] = ID.ele[0][1] = -INF;
n = read(), m = read(), read();
FOR(i, 1, n) p[i] = read(), sump += p[i];
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, n, 1);
FOR(i, 1, m)
{
int a = read(), x = read(), b = read(), y = read();
if (!x && !y && (fa[a] == b || fa[b] == a))
{
puts("-1");
continue;
}
ll a0 = p[a], b0 = p[b], tmp = 0;
if (!x) modify(a, INF), tmp += INF - a0; else modify(a, -INF);
if (!y) modify(b, INF), tmp += INF - b0; else modify(b, -INF);
Matrix<2, 1> ans = query(1);
#define ANS ans.ele
printf("%lld\n", sump - max(ANS[0][0], ANS[1][0]) + tmp);
modify(a, a0), modify(b, b0);
#undef ANS
}
return 0;
}

其他做法

不会,先咕咕咕。

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme