作者：DaybreakCP | 来源：互联网 | 2023-06-06 16:12
Solution简化版看了简化版之后容易想到一个dp。$dp_{u,0}$代表$u$的子树内不选$u$的最大答案。$dp_{u,1}$代表$u$的子树内选$u$的最大答案。有转移方
Solution
简化版
看了简化版之后容易想到一个dp。
$dp_{u,0}$代表$u$的子树内不选$u$的最大答案。
$dp_{u,1}$代表$u$的子树内选$u$的最大答案。
有转移方程：
$dp_{u,0}=\sum_{(u,v) \in E} max(dp_{v,0}, dp_{v,1})$。
$dp_{u,1}=(\sum_{(u,v) \in E} dp_{v,0})+a_u$。
然后对于ddp的模板题我们就得到了一个$O(nm)$的优秀算法。
接下来我们就来看看怎么用ddp的套路来切掉这道题。
变成序列dp的形式
因为ddp只是利用树剖把树剖成一条条链，然后再链上做ddp，所以我们要有一个适应链dp的方程和状态。
我们在树剖时只能处理重边的结果，不能处理轻边的结果，所以我们要先把轻边的结果算出来。
设$u$的重儿子为$son(u)$。
因为是在重链上序列dp，所以我们要先把重儿子分离出来。
令$g_{u,0}=\sum_{v \ne son(u)} max(dp_{v,1},dp_{v,0})$，$g_{u,1}=(\sum_{v \ne son(u)} dp_{v,0}) + a_u$。
则有$dp_{u,0}=g_{u,0}+max(dp_{son(u),0}, dp_{son(u),1})$，$dp_{u,1}=g_{u,1}+dp_{son(u),0}$。
我们发现能做ddp还有一个前提是变成序列dp后可以用广义矩乘来表示转移，比如上面的例子可以表示成：
$\left[ \begin{matrix} g_{u,0} & g_{u,0} \\ g_{u,1} & -inf \end{matrix} \right] \times \left[ \begin{matrix} dp_{son(u),0} \\ dp_{son(u),1} \end{matrix} \right]=\left[ \begin{matrix} dp_{u,0} \\ dp_{u,1} \end{matrix} \right] $
然后我们就可以愉快的ddp了！要想查任意点的dp值只需查从它这个点到它所在的重链的结尾上的点的矩阵乘积即可（所以我们还需维护链尾），因为链尾的矩阵即为其dp值矩阵。
而这个$g$数组和$dp$数组都是可以在树链剖分时预处理出来的。
修改
我们发现我们只需修改$g$的值，即矩阵即可。
对于一个位置先把它的修改了，然后跳到它的链头的父亲，继续循环做直到到根。
为什么可以这么做因为$g$是与重链无关的，只用修改轻链的情况。
具体修改时需要记录前一个点（即前一条重链的联投）的dp值修改前后的增量，然后用之前的值加上其即可（因为是修改一个轻儿子）。
具体可看代码。
查询
查询时查根的dp值即可。
Code
#include
#include
#include
using namespace std;
const int N = 100010;
//输入输出
template void read(T &x) {
int f = 1; char ch = getchar(); x = 0;
for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - ‘0‘;
x *= f;
}
template void write(T x) {
if (x > 9) write(x / 10);
putchar(x % 10 + ‘0‘);
}
template void print(T x) {
if (x <0) x = -x, putchar(‘-‘);
write(x);
putchar(‘\n‘);
}
template void cmax(T &x, T y) {if (y > x) x = y;}
template void cmin(T &x, T y) {if (y y;}
int n;//节点个数
int m;//操作个数
int a[N];//初始值
int dp[N][2];//dp数组
//前向星
namespace QXX{
struct node{
int pre, to;
}edge[N <<1];
int head[N], tot;
inline void add(int u, int v) {//加边
edge[++tot].pre = head[u];
edge[tot].to = v;
head[u] = tot;
}
}using namespace QXX;
//矩阵
namespace MATRIX{
struct Matrix{
int arr[3][3];
}A[N];
inline void init(Matrix &X) {memset(X.arr, 0xcf, sizeof(X.arr));}
inline Matrix Mul(Matrix X, Matrix Y) {
Matrix Z;
init(Z);
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= 2; j++)
for (int k = 1; k <= 2; k++)
cmax(Z.arr[i][j], X.arr[i][k] + Y.arr[k][j]);
return Z;
}
}using namespace MATRIX;
//树链剖分
namespace TCP{
int dfn[N], num;//dfs 序
int top[N];//链头
int End[N];//链尾
int pos[N];//pos[i] 代表 dfs 序为 i 的节点是哪个
int sz[N];//子树大小
int fa[N];//父亲
int son[N];//重儿子
void dfs1(int x) {//预处理子树大小、父亲和重儿子
sz[x] = 1;
for (int i = head[x]; i; i = edge[i].pre) {
if (fa[x] == edge[i].to) continue;
fa[edge[i].to] = x;
dfs1(edge[i].to);
sz[x] += sz[edge[i].to];
if (sz[edge[i].to] > sz[son[x]])
son[x] = edge[i].to;
}
}
void dfs2(int x, int chain) {//树链剖分预处理
dfn[x] = ++num, top[x] = chain, pos[num] = x;
init(A[x]);
A[x].arr[1][1] = A[x].arr[1][2] = 0;
A[x].arr[2][1] = a[x];
if (son[x])
dfs2(son[x], chain), dp[x][0] = max(dp[son[x]][1], dp[son[x]][0]), dp[x][1] = dp[son[x]][0];//加上重链信息
else
End[chain] = dfn[x];
for (int i = head[x]; i; i = edge[i].pre) {//处理轻儿子
if (edge[i].to == fa[x] || edge[i].to == son[x])
continue;
dfs2(edge[i].to, edge[i].to);
A[x].arr[1][1] += max(dp[edge[i].to][1], dp[edge[i].to][0]);
A[x].arr[1][2] = A[x].arr[1][1];
A[x].arr[2][1] += dp[edge[i].to][0];
}
dp[x][0] += A[x].arr[1][1];
dp[x][1] += A[x].arr[2][1];
}
}using namespace TCP;
namespace Segment_Tree{
struct Segment{
Matrix val;
}tr[N <<2];
inline void push_up(int p) {tr[p].val = Mul(tr[p <<1].val, tr[p <<1 | 1].val);}
void build(int p, int l, int r) {
if (l == r) {
tr[p].val = A[pos[l]];
return;
}
int mid = (l + r) >> 1;
build(p <<1, l, mid);
build(p <<1 | 1, mid + 1, r);
push_up(p);
}
void change(int p, int l, int r, int Pos) {
if (l == r) {
tr[p].val = A[pos[l]];
return;
}
int mid = (l + r) >> 1;
if (Pos <= mid) change(p <<1, l, mid, Pos);
else change(p <<1 | 1, mid + 1, r, Pos);
push_up(p);
}
Matrix query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tr[p].val;
}
int mid = (l + r) >> 1;
if (R <= mid) return query(p <<1, l, mid, L, R);
else if (L > mid) return query(p <<1 | 1, mid + 1, r, L, R);
else return Mul(query(p <<1, l, mid, L, mid), query(p <<1 | 1, mid + 1, r, mid + 1, R));
}
}using namespace Segment_Tree;
int main() {
read(n); read(m);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1, u, v; i i) {
read(u); read(v);
add(u, v);
add(v, u);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
while (m--) {
int x, y;
read(x); read(y);
A[x].arr[2][1] += y - a[x];
a[x] = y;
while (x != 0) {
Matrix bef = query(1, 1, n, dfn[top[x]], End[top[x]]);
change(1, 1, n, dfn[x]);
Matrix aft = query(1, 1, n, dfn[top[x]], End[top[x]]);
x = fa[top[x]];
A[x].arr[1][1] += max(aft.arr[1][1], aft.arr[2][1]) - max(bef.arr[1][1], bef.arr[2][1]);
A[x].arr[1][2] = A[x].arr[1][1];
A[x].arr[2][1] += aft.arr[1][1] - bef.arr[1][1];
}
Matrix ans = query(1, 1, n, top[1], End[top[1]]);
print(max(ans.arr[1][1], ans.arr[2][1]));
}
return 0;
}
京公网安备 11010802041100号