F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 3626. -- [LNOI2014]LCA

3626: [LNOI2014]LCA

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 4115  Solved: 1702
[Submit][Status][Discuss]

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。


Source

数据已加强 by saffah

[Submit][Status][Discuss]

HOME Back