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

  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$的路径数。