#d48x79. LCA

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

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

题目描述

给出一个 $n$ 个节点的有根树（编号为 $0$ 到 $n-1$ ，根节点为 $0$ ）。

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

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

有 $m$ 次询问，每次询问给出 $l, r, z$ ，求 $\sum_{i=l}^r dep[\text{LCA}(i,z)]$ 。

第一行 $2$ 个整数， $n, m$ 。

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

接下来 $m$ 行，每行 $3$ 个整数， $l, r, z$ 。

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

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$ 。