本文旨在让读者背代码 这绝对是全网最长的树剖文章 前言 在做题时,我们可能会遇到这样一类问题: 给定一棵 个结点的树和 次操作,操作有两种,一种是给定两个结点,让连接两个结点的路径上的所有点权值加上一个值,另一种是查询路径上所有点的权值和。,。 如果是最后统一输出结点权值,用树上差分+dfs 就能轻松水过,而对于在线查询,如果数据范围小的话暴力即可 AC,时间复杂度 ,但是很明显,这个数据范围肯定不能这么写了。此时,就需要树链剖分出场了。 树链剖分 原理 树链剖分是根据轻重儿子,将一棵树剖成多条链,然后就可以用数据结构来维护这些链了,听着似乎还是有点像暴力,不过因为一条链有多个结点,所以可...