Problem Description

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$.

Input Format

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 Format

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

4 2 3
1
1
3

7

Hint

[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