标签为 [树链剖分] 的文章

BZOJ3626 LCA

题目大意 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先 有q次询问,每次询问给出l r z,求$\sum_{i=l}^{r}deep[LCA(i,z)]$ 题解 做这题,首先要发现一个事实:两个点的LCA的深度就是两个点分别到根的链的公共点 所以,对于一次询问,可以将[l,r]区间内的点到根的链的每一个的权值+1,答案即为z到根的链上的点的权值和 这个是可以用树链剖分维护的 对于多次询问,我们将一个询问变成[1,l-1]和[1,r]两个询问,将询问排序,一边更新 ......