给出一棵树和一些操作,每次操作都将两点间所有经过的点的点权+1,求出点权最大的点的权值。
链接
题解
怎么说呢,一道树上点差分模板题,当然树链剖分也可以做。
定义$diff[i]$为点$i$的差分值,那么对于每一次修改的参数$start$和$end$,将$diff[start++,diff[end++,diff[\operatorname{lca}(start,end)—]$。为了不让路线修改蔓延到祖先,把LCA的父节点的差分值-1。
最后用DFS求出子树差分数组的和就得到该节点修改后的点权啦。
代码
1 |
|