树上差分

1.点差分(根结点要加一个虚拟节点)
L->R +v
L+=v
R+=v
lca-=v;
lca父亲-=v
最后,进行一个dfs,一个节点的点权等于它所有子节点点权和+自己点权
2.边差分
L->R +v
L+=v
R+=v
lca-=2*v
最后,dfs,父节点到子节点路径的边权,为原边权+子节点点权(这里子节点已经完成了自己的点权累加),然后改变父节点的点权

posted @ 2025-11-26 22:31  江海一归客  阅读(10)  评论(0)    收藏  举报