4560: 「LNOI2014」LCA
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给出一个 $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$。