Background

You've been ordered to start the mission now.

The interception op was a success, enemy air units around Khesed have been weakened, and the Republic of Emmeria's military has taken advantage of this prime opportunity to initiate a counterattack operation with all forces participating.

Enemy forces have established a wide-scale defensive line around Sipli Field, consisting largely of tank battalions.

Our ground forces are set up to cross the river and penetrate it, and eventually gain control of Khesed.

Garuda Team, we need you to support our advancing ground units, and eliminate all enemy forces. Multiple units will be simultaneously carrying out various operations on the ground.

Pay attention to the airspace above each operation area, and provide support as needed.

This must be the first time you've ever participated in a mission of this scale.

The battle simulator is a good way to get some practical experience under your belt.

Godspeed.

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 03} \\\Large\text{Sipli Field}\\\tiny -\textit{ Fortunes of War }-$$

Problem 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