树上差分

· · 个人记录

差分是一种简单易写的 trick ，主要处理区间修改（加减）

的问题，当它上树后就成为了树上差分

1 覆盖点

前置知识：LCA

注意点：

return f[x][0];//不能漏写
if(f[x][i]>0&&Depth[f[x][i]]>=Depth[y])x=f[x][i];//f[x][i]>0

核心思路

对于覆盖点对 (s,t) 覆盖 s -> t 的路径

将其分成 s -> lca(s,t) 和 lca(s,t) -> t 两段进行处理

令 tag_s++ tag_t++ tag_{lca(s,t)}-- tag_{father_{lca(s,t)}}-- 即可

最后用一遍 dfs 统计答案即可

例题 Max flow

松鼠的新家

2 覆盖边

（先咕着，还没学）