树上差分最经典的两种套路
- 给定特殊的点,让你求一条路径上有多少个这样的点
- 给定带权的路径,让你求不经过一个点的路径中的最大值。
第一种相对好处理,一般会有离线和在线两种方法,
离线的方法相对直观,就是树剖。
在线的方法,要用到树上差分,多数要用上可持久化。
考虑一个点$x$,什么样的路径可能被它贡献。
也就是一端在$x$子树内,一端在$x$子树外。
换言之,在$x$子树内的点的路径,都有可能被它贡献$+1$。
统计时差分一下就好了,$s_x+s_y-s_{lca(x,y)}-s_{fa_{lca(x,y)}}$。
第二类不那么直观,
首先考虑什么样的路径会经过$x$。
其一头势必经过$x$子树(含$x$)中某一个点,换言之,只有$x$子树中的点可能对当前询问产生贡献。
另一头势必在$x$子树外(含$x$)某一点,换言之,要减去在子树内的不经过$x$的路径数。
因此每添加一条路径$(x,y)$,$x,y$处$+1$,$lca(x,y),fa(lca(x,y))$处$-1$。
统计$x$子树权值和就是经过$x$的路径数。
最后一次更新于2020-04-01
0 条评论