OI Problems   关于

#d48x79. LCA

时间限制:1 s       空间限制:125 MiB       标签: 图论 树链剖分 重链剖分 数据结构 线段树 省选 辽宁 2014 

算法难度等级:6       思维难度等级:5       实现难度等级:5


本题来源于:辽宁 2014 年省队选拔

题目描述

给出一个 nn 个节点的有根树(编号为 00n1n-1,根节点为 00)。

一个点的深度定义为这个节点到根的距离 +1+1

dep[i]dep[i] 表示点 ii 的深度,LCA(i,j)\text{LCA}(i, j) 表示 iijj 的最近公共祖先。

mm 次询问,每次询问给出 l,r,zl, r, z,求 i=lrdep[LCA(i,z)]\sum_{i=l}^r dep[\text{LCA}(i,z)]

输入格式

第一行 22 个整数,n,mn, m

接下来 n1n-1 行,分别表示点 11 到点 n1n-1 的父节点编号。

接下来 mm 行,每行 33 个整数,l,r,zl, r, z

输出格式

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

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

提示

对于 20%20\% 的数据,n10000,m10000n\le 10000,m\le 10000

对于 40%40\% 的数据,n20000,m20000n\le 20000,m\le 20000

对于 60%60\% 的数据,n30000,m30000n\le 30000,m\le 30000

对于 80%80\% 的数据,n40000,m40000n\le 40000,m\le 40000

对于 100%100\% 的数据,1n50000,1m500001\le n\le 50000,1\le m\le 50000