LCA Depth Sum Queries

Given a rooted tree with \(n\) nodes (numbered from \(0\) to \(n-1\), with node \(0\) as the root). The depth of a node is defined as the distance from the node to the root plus one. That is, the depth of node \(i\) is \(dep[i] = \text{distance}(i, 0)+1\).

Let \(\operatorname{LCA}(i, j)\) denote the lowest common ancestor of nodes \(i\) and \(j\). You are given \(m\) queries. Each query provides three integers \(l\), \(r\), and \(z\). For each query, you are to compute:

\(\sum_{i=l}^{r} dep[\operatorname{LCA}(i, z)]\)

where \(dep[\operatorname{LCA}(i, z)]\) denotes the depth of the lowest common ancestor of nodes \(i\) and \(z\).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of nodes in the tree and the number of queries, respectively.

The second line contains \(n-1\) space-separated integers. The \(i\)-th integer (for \(1 \le i \le n-1\)) indicates the parent of node \(i\). (Note that node \(0\) is the root and has no parent.)

Each of the next \(m\) lines contains three integers \(l\), \(r\), and \(z\), representing a query.

outputFormat

For each query, output a single line containing the corresponding sum \(\sum_{i=l}^{r} dep[\operatorname{LCA}(i,z)]\).

sample

5 3
0 0 1 1
1 3 3
0 4 2
2 4 4

6
6
6