【题解】P4719 【模板】动态 DP（线段树版本）

P4719 【模板】动态 DP - 洛谷动态 dp新东西猫娘学习。希望我贫瘠的线性代数知识能帮到你。0.导入不考虑修改操作这只是简单的树上 dp即没有上司的晚会。但每次修改单个点权如果重新跑整棵树 DP 是的无法满足大数据。我们希望能支持单点修改并快速获得根的状态。常方法是对树做轻重链剖分。考虑到 DP 转移是固定的把每个节点的 DP 转移写成线性变换用矩阵表示。从而一条重链上的 DP 可以用线段树维护矩阵乘积。修改一个点权时只更新该点到根路径上涉及的重链的线段树实际是“跳链”更新。1.矩阵相关可能有人对矩乘还不熟悉那我这里再解释下。中第一行第一列的配上第一行第一列的可以贡献第一行第一列的。中第一行第二列的配上第二行第一列的可以贡献第一行第一列的。中第二行第一列的配上第一行第一列的可以贡献第二行第一列的。中第二行第二列的配上第二行第一列的可以贡献第二行第一列的。2.重链内维护我们把每个点按照重链剖分后给每条重链分配一个线段树线段树节点存储该区间内矩阵的乘积按链顺序从浅到深相乘。对于叶子节点重儿子不存在我们定义它的“重儿子”矩阵为单位矩阵。每个点维护自己的矩阵然后一条重链的顶端节点向上传给父节点时用该链的矩阵乘积得到顶端的 DP 值进而更新父节点的轻儿子贡献。当修改点的权值为更新点的矩阵​ 中的然后从开始沿着重链向上更新对于当前节点重新计算它所在重链的线段树得到这条重链顶端的 DP 向量。如果这条链的顶端是那么的父节点的轻儿子贡献可能发生变化因此需要更新的​ 或​。然后继续向上处理父节点所在的重链直到根。每次修改涉及的链数量是因为轻边数量是。每条链上的线段树更新是所以总复杂度。3.代码#includebits/stdc.h using namespace std; const int N 1e5 10; const int inf 0x3f3f3f3f; #define lc(p) (p 1) #define rc(p) ((p 1) | 1) #define mid ((l r) 1) int n, m; int a[N]; vectorint G[N]; int fa[N], siz[N], son[N]; // 父亲、子树大小、重儿子 int f[N][2]; // 静态DPf[x][0/1] 表示x不选/选时的子树最大权 int dfn[N], id[N], top[N], bot[N], tsp; // dfn[x]节点 x 的 dfs 序时间戳id[t]dfs序 t 对应的节点编号 // top[x]x 所在重链的链头节点bot[top]链头 top 所在链的链尾节点的 dfs 序即链的区间右端点 // tspdfs 序计数器 // 第一次 DFS处理 fa, siz, son并计算静态 DP 初值 void dfs(int x) { siz[x] 1; f[x][1] a[x]; // 选 x初始贡献为自己的权值 for (int y : G[x]) if (fa[x] ! y) { fa[y] x; dfs(y); siz[x] siz[y]; if (siz[y] siz[son[x]]) { son[x] y; // 更新重儿子 } // 正常树上 DP 转移 f[x][0] max(f[y][0], f[y][1]); // x 不选儿子可选可不选 f[x][1] f[y][0]; // x 选儿子必须不选 } } // 第二次 DFS树链剖分分配 dfs 序确定 top 和 bot void dfs(int x, int tp) { dfn[x] tsp; id[tsp] x; top[x] tp; bot[tp] tsp; // 更新链尾的 dfn因为 dfs 序连续最后遍历到的就是链尾 if (son[x]) { dfs(son[x], tp); // 优先重儿子保持链上dfs序连续 } for (int y : G[x]) if (y ! fa[x] y ! son[x]) { dfs(y, y); // 轻儿子开新链 } } // ---------- 矩阵结构体用于动态DP的转移矩阵 ---------- struct Matrix { int g[2][2]; // 重载乘法广义矩阵乘法max-plus Matrix operator*(Matrix b) { Matrix t; memset(t.g, -0x3f, sizeof(t.g)); for (int i 0; i 1; i ) for (int j 0; j 1; j ) for (int k 0; k 1; k ) t.g[i][j] max(t.g[i][j], g[i][k] b.g[k][j]); return t; } } mt[N], tr[N 2]; // mt[x]节点x的转移矩阵仅考虑轻儿子贡献 // tr[p]线段树节点维护一段 dfs 序区间的矩阵乘积 void pushup(int p) { tr[p] tr[lc(p)] * tr[rc(p)]; } void build(int p, int l, int r) { if (l r) { int x id[l]; // 当前dfs序对应的节点 int g0 0, g1 a[x]; // g0: x 不选g1: x 选 // 遍历轻儿子非重儿子、非父亲累加其DP值 for (auto y : G[x]) { if (y ! fa[x] y ! son[x]) { g0 max(f[y][0], f[y][1]); // x 不选时轻儿子任意 g1 f[y][0]; // x 选时轻儿子不选 } } // 构造转移矩阵 // g[0][0] g[0][1] g0 不选 x 时当前链状态任意下一状态也是不选 // g[1][0] g1 选 x下一状态必须不选 // g[1][1] -inf 选 x 后不能转移到选因为相邻不能同时选 tr[p] mt[x] {g0, g0, g1, -inf}; return ; } build(lc(p), l, mid); build(rc(p), mid 1, r); pushup(p); } // 线段树单点更新 void change(int p, int l, int r, int x) { if (x l || r x) { return ; } if (l r) { tr[p] mt[id[l]]; return; } change(lc(p), l, mid, x); change(rc(p), mid 1, r, x); pushup(p); } // 线段树区间查询返回区间 [x, y] 的矩阵乘积 Matrix query(int p, int l, int r, int x, int y) { if (x l r y) { // 必须刚刚好 return tr[p]; } if (y mid) return query(lc(p), l, mid, x, y); if (x mid) return query(rc(p), mid 1, r, x, y); // 跨区间先左后右注意乘法顺序左乘右 return query(lc(p), l, mid, x, mid) * query(rc(p), mid 1, r, mid 1, y); } // 动态 DP 核心修改点权并更新所有影响 void update(int u, int k) { // 更新点 u 的转移矩阵中关于 “选 u” 的项轻儿子贡献不变只变自身权值 mt[u].g[1][0] k - a[u]; a[u] k; // 更新权值 // 从 u 开始沿重链向上更新直到根 while (u) { // 先查询当前 u 所在链的旧矩阵乘积整条链的转移 Matrix old query(1, 1, n, dfn[top[u]], bot[top[u]]); // 将 u 的叶子节点在线段树中更新此时 mt[u] 已变 change(1, 1, n, dfn[u]); // 查询更新后该链的新矩阵乘积 Matrix now query(1, 1, n, dfn[top[u]], bot[top[u]]); // 当前链的矩阵变化会影响其父链当前链头作为父节点的一个轻儿子 // 因此需要更新父节点即链头 top[u] 的父亲的轻儿子贡献。 u fa[top[u]]; // 跳转到父链的节点即当前链头的父亲 if (!u) break; // 到达根的上方结束 // 根据新旧链矩阵的DP结果差值更新父节点u的轻儿子贡献 // old 和 now 的 g[0][0] 和 g[1][0] 分别代表该链头节点不选/选时的最大权 // 父节点 u 不选时轻儿子可任意 // 所以要加上 max(now.g[0][0], now.g[1][0]) - max(old.g[0][0], old.g[1][0]) mt[u].g[0][0] max(now.g[0][0], now.g[1][0]) - max(old.g[0][0], old.g[1][0]); mt[u].g[0][1] mt[u].g[0][0]; // g[0][0] 和 g[0][1] 相同因为不选时下一状态任意 // 父节点 u 选时该轻儿子必须不选所以变化量为 now.g[0][0] - old.g[0][0] mt[u].g[1][0] now.g[0][0] - old.g[0][0]; // 注意mt[u].g[1][1] 始终为 -inf保持不变 } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i ) { cin a[i]; } for (int i 1; i n; i) { int x, y; cin x y; G[x].push_back(y); G[y].push_back(x); } fa[1] 0; tsp 0; memset(son, 0, sizeof(son)); dfs(1); // 第一次 DFS求 fa, size, son, 静态 DP dfs(1, 1); // 第二次 DFS树链剖分分配 dfn build(1, 1, n); while (m --) { int x, y; cin x y; update(x, y); Matrix ans query(1, 1, n, dfn[1], bot[1]); // 查询整棵树根 1 所在链的矩阵 cout max(ans.g[0][0], ans.g[1][0]) \n; } return 0; }