Description

Given a tree with $n$ nodes and two constants $L, R$.

For each node $u$, find how many paths pass through $u$ and have length $d \in [L, R]$.

Input Format

The first line contains three integers $n, L, R$.

The next line contains $n - 1$ integers. The $i$-th integer $f_i$ indicates that there is an undirected edge $f_i \leftrightarrow i + 1$.

Output Format

Output $n$ lines, each containing one integer, representing the answer for the corresponding node.

5 1 3
1 1 2 2

7
9
4
4
4

Hint

Explanation for Sample 1:

• Paths passing through $1$: 1-2, 1-3, 1-4, 1-5, 2-3, 4-3, 5-3.
• Paths passing through $2$: 2-1, 2-3, 2-4, 2-5, 1-4, 1-5, 3-4, 3-5, 4-5.
• Paths passing through $3$: 3-1, 3-2, 3-4, 3-5.
• Paths passing through $4$: 4-1, 4-2, 4-3, 4-5.
• Paths passing through $5$: 5-1, 5-2, 5-3, 5-4.

• Subtask 1 (3 pts): $R = 1$.
• Subtask 2 (7 pts): $R \leq 2$.
• Subtask 3 (10 pts): $n \leq 100$.
• Subtask 4 (10 pts): $n \leq 2\times 10^3$.
• Subtask 5 (15 pts): $n \leq 10^5, L = 1, R = n$.
• Subtask 6 (15 pts): $n \leq 10^5, L = R$.
• Subtask 7 (20 pts): $n \leq 10^5$.
• Subtask 8 (20 pts): No special constraints.

For $100\%$ of the testdata, it holds that $1 \leq n \leq 10^6$, $1 \leq L \leq R \leq n$.

Idea: _Solowing_ClCN, solution: _Solowing_ClCN, code: _Solowing_ClCN, data: _Solowing_ClCN.

Translated by ChatGPT 5