题目描述
给出一个 n 个节点的有根树(编号为 0 到 n−1,根节点为 0)。一个点的深度定义为这个节点到根的距离 +1。
设 dep[i] 表示点i的深度,LCA(i,j) 表示 i 与 j 的最近公共祖先。
有 q 次询问,每次询问给出 l r z,求 l≤i≤r∑dep[LCA(i,z)]。
输入格式
第一行 2 个整数 n,q。
接下来 n−1 行,分别表示点 1 到点 n−1 的父节点编号。
接下来 q 行,每行 3 个整数 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。