P10421 [Lanqiao Cup 2023 National A] Paths on a Tree

Given a tree with $n$ nodes, where the length of every edge is $1$, find the sum of lengths of all paths in this tree whose lengths are between $L \sim R$. Two paths are considered the same path if the sets of edges they pass through are exactly the same. That is, compute $\sum\limits_{i=1}^n{\sum\limits_{j=i+1}^{n}{dis(i,j)\cdot[L \le dis(i,j) \le R]}}$, where $dis(i,j)$ denotes the distance between node $i$ and node $j$, and $[C]$ equals $1$ if condition $C$ holds, otherwise $0$.

The first line contains three integers $n, L, R$, separated by one space. The next $n - 1$ lines each contain one integer. On the $i$-th line, the integer $F_i$ indicates the parent node of node $i + 1$ in the tree. Node $1$ is the root and has no parent.

Output one line containing one integer, which is the answer.

**[Test Case Size and Conventions]** For $40\%$ of the testdata, $n \le 2000$. For all testdata, $1 \le L \le R \le n \le 10^6$, $1 \le F_i \le i$. Translated by ChatGPT 5