主题

主题

 
   

3626: [LNOI2014]LCA

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3626

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。


个人解法:

抄题解。毕竟题目太神本蒟太菜。

(我习惯点用[1..n]而不是[0..n-1],于是下文叙述可能会与原题有所不同)

首先,考虑一次询问:

如果把点集的点x到root的路径全部+1,那么查询z与点集的点x与z的lca的深度就是z到根的路径的点权和。

于是我们把查询的[l..r]的转换为查询[1..l-1]到[1..r]的。

那么我们就依次加入点1到n(即把这个点x到root的路径+1),然后到查询的时候就去查询到根的路径。

尝试了一下用LCT实现树上链加和树上点权查询。虽然理论上O(nlogn),似乎我的常数炒鸡大。总共跑了1700ms的样子。

原来把我的变量名缩短,可以把程序缩短如此之多……

不过用LCT的时候注意的是,在Access同样需要Pushdown。不过只需要Pushdown一些节点,不必把其周围所有节点都Pushdown。


代码如下:

https://code.csdn.net/snippets/2172979

 
 
评论