【bzoj3626】[LNOI2014]LCA

2014年7月28日6,23510

Description

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

Input

第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。

Output

输出q行,每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

8
5

HINT

共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。

题解

直接引用清华爷gconeice的题解吧

显然,暴力求解的复杂度是无法承受的。
考虑这样的一种暴力,我们把 z 到根上的点全部打标记,对于 l 到 r 之间的点,向上搜索到第一个有标记的点求出它的深度统计答案。观察到,深度其实就是上面有几个已标记了的点(包括自身)。所以,我们不妨把 z 到根的路径上的点全部 +1,对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现,实际上这个操作具有叠加性,且可逆。也就是说我们可以对于 l 到 r 之间的点 i,将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点(包括自身)的权值和就是这个询问的答案。把询问差分下,也就是用 [1, r] − [1, l − 1] 来计算答案,那么现在我们就有一个明显的解法。从 0 到 n − 1 依次插入点 i,即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和,显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n),LCT的复杂度为 O((n + q)· log n),均可以完成任务。至此,题目已经被我们完美解决。

非常清楚啊,接下来是吐槽

妈蛋这道题完全没有裸暴力分T T

还有其实这题根本不用会求lca,根本用不到倍增T T

 

 

 

  • wulala2014年10月22日 上午9:09 回复

    跪跪跪orz

    #1  
  • SkyDec2014年10月26日 下午9:51 回复

    跪跪跪orz

    #2  
  • 李有为2014年10月27日 下午4:26 回复

    跪跪跪orz

    #3  
  • willinglive2014年10月27日 下午8:01 回复

    跪跪跪orz

    #4  
  • 何俊2015年10月22日 下午5:25 回复

    跪跪跪orz

    #5  
  • Clare2015年10月22日 下午5:30 回复

    跪跪跪orz

    #6  
  • 褚步霄2016年7月29日 下午2:40 回复

    跪跪跪orz

    #7  
  • 斯巴达临时工2017年2月8日 上午9:49 回复

    跪跪跪orz

    #8  
  • - 慕°2017年2月21日 上午9:34 回复

    弱弱地问一句,为啥黄学长每道题都要AC好几遍啊

    #9  
  • limfc2017年8月11日 下午3:08 回复

    跪跪跪orz

    #10