修改时向上跳重链,获取当前重链的时候,答案矩阵要从重链顶乘到重链底而不是从 u 开始乘。
正确代码:
void pathUpd(int u, int w) {
inital[dfn[u]][1][2] += w - a[u];
a[u] = w;
while (u) {
Matrix<1, 2> before, after; // 更改需要计算差值
// 注意,这里有个大坑点!
// 重链的 dp 值要一直乘到链顶而不是乘到 u
before = zero * query(dfn[top[u]], term[top[u]]);
update(dfn[u]);
after = zero * query(dfn[top[u]], term[top[u]]);
u = fa[top[u]];
inital[dfn[u]][1][1] += -max(before[1][1], before[1][2]) + max(after[1][1], after[1][2]);
inital[dfn[u]][2][1] = inital[dfn[u]][1][1];
inital[dfn[u]][1][2] += -before[1][1] + after[1][1];
}
}
错误代码:
void pathUpd(int u, int w) {
inital[dfn[u]][1][2] += w - a[u];
a[u] = w;
while (u) {
Matrix<1, 2> before, after; // 更改需要计算差值
before = zero * query(dfn[u], term[top[u]]);
update(dfn[u]);
after = zero * query(dfn[u], term[top[u]]);
u = fa[top[u]];
inital[dfn[u]][1][1] += -max(before[1][1], before[1][2]) + max(after[1][1], after[1][2]);
inital[dfn[u]][2][1] = inital[dfn[u]][1][1];
inital[dfn[u]][1][2] += -before[1][1] + after[1][1];
}
}