在树上做线段树合并的时候,我们一般在完成一个节点的合并操作后立即计算当前点的贡献,如下面的代码所示:
inline void dfs(int u) {
//...
change(rt[u], ...); //更新当前点
for (int v : ...) {
//...
merge(a, b, ...); //合并
}
//...
query(rt[u], ...) //计算当前点的贡献
}
然而,如果在完成所有的合并之后再计算贡献,如下面的代码所示:
inline void dfs(int u) {
//...
change(rt[u], ...); //更新当前点
for (int v : ...) {
//...
merge(a, b, ...); //合并
}
}
int main() {
//...
for (int i = 1; i <= n; i++) {
//...
query(rt[u], ...) //计算当前点的贡献
}
}
为什么后者是错误的?