题目描述

给出一个 $n$ 个节点的有根树（编号为 $0$ 到 $n-1$，根节点为 $0$）。一个点的深度定义为这个节点到根的距离 $+1$。

设 $dep_i$ 表示点 $i$ 的深度，$LCA(i,j)$ 表示 $i$ 与 $j$ 的最近公共祖先。

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

（即，求在 $[l,r]$区间内的每个节点 $i$ 与 $z$ 的最近公共祖先的深度之和）

输入格式

第一行两个整数 $n,q$。

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

接下来 $q$ 行，每行三个整数 $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$。

题目来源

数据已加强 by saffah