[LNOI2014] LCA
题目描述
给出一个 \(n\) 个节点的有根树（编号为 \(0\) 到 \(n-1\)，根节点为 \(0\) ）。
一个点的深度定义为这个节点到根的距离 \(+1\)。
设 \(dep[i]\) 表示点 \(i\) 的深度，\(\operatorname{LCA}(i, j)\) 表示 \(i\) 与 \(j\) 的最近公共祖先。
有 \(m\) 次询问，每次询问给出 \(l, r, z\)，求 \(\sum_{i=l}^r dep[\operatorname{LCA}(i,z)]\) 。
输入格式
第一行 \(2\) 个整数，\(n, m\)。
接下来 \(n-1\) 行，分别表示点 \(1\) 到点 \(n-1\) 的父节点编号。
接下来 \(m\) 行，每行 \(3\) 个整数，\(l, r, z\)。
输出格式
输出 \(q\) 行，每行表示一个询问的答案。每个答案对 \(201314\) 取模输出。
样例 #1
样例输入 #1
5 2
0
0
1
1
1 4 3
1 4 2
样例输出 #1
8
5
提示
对于 \(20\%\) 的数据，\(n\le 10000,m\le 10000\)；
对于 \(40\%\) 的数据，\(n\le 20000,m\le 20000\)；
对于 \(60\%\) 的数据，\(n\le 30000,m\le 30000\)；
对于 \(80\%\) 的数据，\(n\le 40000,m\le 40000\)；
对于 \(100\%\) 的数据，\(1\le n\le 50000,1\le m\le 50000\)。