树上差分

一句话理解

树上差分：路径加变成点差分。

为什么要学

链上加、子树加。

讲解

点差分：a[u]+=w, a[v]+=w, a[lca]-=w, a[fa[lca]]-=w。再 DFS 下推或上推。

例子

和序列差分同一思想，在树上用 LCA。

常见错误

• lca 减一次还是两次搞错（点/边差分不同）。
• 没 DFS 还原。