[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)

发布于 2018-01-20  18 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)

Description

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。有q次询问,每次询问给出l r z,求\(\sum_{l<=i<=r}dep[LCA(i,z)]\)。(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)

Http

BZOJ

Tag

树链剖分,离线

解决思路

先考虑单次询问,如果我们对于点\(i \in [l,r]\),都把\(i\)到根的路径加一,那么从我们询问的点到根的路径权值之和就是此次询问的答案。
处理路径覆盖,我们可以采用树链剖分+线段树的方式实现。
现在考虑多组数据,我们可以离线操作,把输入读进来排序,记录左端点和右端点分别处理,这样就可以回答多组询问了。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)


HNCJ OIer 一枚