DDP 模板,定义
g(x,0)=∑x=son(x)max{f(v,0),f(v,1)}
g(x,1)=v=son(x)∑f(v,0)+ax
那么在 access 的时候,由于改变虚实,需要改变 g,照理来说应该需要对应的 f 值。
但是,如下是日报的实现:
// access按照维护虚子树信息的方法写
inline void access(int x) {
for (int y = 0; x; x = fa[y = x]) {
splay(x);
// 原来的右孩子由实变虚,要将它的贡献计入g
if (ch[x][1]) {
val[x].data[0][0] += std::max(prd[ch[x][1]].data[0][0], prd[ch[x][1]].data[1][0]);
val[x].data[1][0] += prd[ch[x][1]].data[0][0];
}
// y变成了实儿子,要将它的贡献从g中减去。
if (y) {
val[x].data[0][0] -= std::max(prd[y].data[0][0], prd[y].data[1][0]);
val[x].data[1][0] -= prd[y].data[0][0];
}
val[x].data[0][1] = val[x].data[0][0];
ch[x][1] = y;
update(x);
}
}
直接调用儿子的矩阵,难道返回的不是 g 值吗?
或者是有一些性质使得这里的 g 和 f 等价?
总之,蒟蒻在这卡住了……问了 luogu academic 群友也未能得解,先在这里求助qwq