标签 树上差分 下的文章

傻逼题,写来放松身心。

考虑到 \displaystyle dep_u^k = \sum_{i=0}^{\infty} dep_{fa^i(u)}^k - dep_{fa^{i+1}(u)}^k,假设我们要求 \displaystyle dep_{\operatorname{lca}(u, v)},可以把 u1 的路径上每个点 x 加上 dep_x^k - dep_{fa(x)}^k 的权值,查询时从 v 向根节点跳把沿途的权值加上即可。

离线所有查询到 x 上,扫描 x,树剖维护修改和查询即可。

READ MORE