P4211 [LNOI2014] LCA

You are given a rooted tree with $n$ nodes (numbered from $0$ to $n - 1$), with root $0$. The depth of a node is defined as its distance to the root $+1$. Let $dep[i]$ denote the depth of node $i$, and let $\operatorname{LCA}(i, j)$ denote the lowest common ancestor of $i$ and $j$. There are $m$ queries. For each query with given $l, r, z$, compute $\sum_{i=l}^{r} dep[\operatorname{LCA}(i, z)]$.

- The first line contains $2$ integers $n, m$. - The next $n - 1$ lines give parent indices: for each $i$ from $1$ to $n - 1$, the $i$-th of these lines contains the parent of node $i$. - The next $m$ lines each contain $3$ integers $l, r, z$.

Output $m$ lines. Each line contains the answer for one query, taken modulo $201314$.

Constraints - For $20\%$ of the testdata, $n \le 10000$, $m \le 10000$. - For $40\%$ of the testdata, $n \le 20000$, $m \le 20000$. - For $60\%$ of the testdata, $n \le 30000$, $m \le 30000$. - For $80\%$ of the testdata, $n \le 40000$, $m \le 40000$. - For $100\%$ of the testdata, $1 \le n \le 50000$, $1 \le m \le 50000$. Translated by ChatGPT 5