关于LCT维护子树信息
查看原帖
关于LCT维护子树信息
592126
13402805827wuaiyang楼主2025/1/21 18:34

当我们要维护复杂信息,例如动态DP中的矩阵,同时要支持换根操作时,我们可不可以通过记录反向的信息(例如原来的顺序是f(s)=f(lc)*val(s)*f(rc),我们新设计类似的g,g(s)=g(rc)*val(s)*g(lc))来在翻转时翻转f和g以维护信息,而在考虑虚子树对父亲的贡献时通过f考虑来维护整体的信息?

2025/1/21 18:34
加载中...