树上差分最经典的两种套路

  1. 给定特殊的点,让你求一条路径上有多少个这样的点
  2. 给定带权的路径,让你求不经过一个点的路径中的最大值。

第一种相对好处理,一般会有离线和在线两种方法,

离线的方法相对直观,就是树剖。

在线的方法,要用到树上差分,多数要用上可持久化。

考虑一个点$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$的路径数。