#2558. 「LNOI2014」LCA

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ldlsn

题目描述

给出一个 n 个节点的有根树(编号为 0 n-1 ,根节点为 0 )。一个点的深度定义为这个节点到根的距离 +1

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

q 次询问,每次询问给出 \texttt{l r z} ,求 \sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]

输入格式

第一行 2 个整数 n,q

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

接下来 q 行,每行 3 个整数 \texttt{l r z}

输出格式

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

样例

样例输入

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

样例输出

8
5

数据范围与提示

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