In the famous company of Limas Agung (Indonesian for Great Pyramid), there are multiple career paths that one can take when dedicating their work into this company. There are $$$N$$$ job titles, each with its own integer salary, and $$$N-1$$$ promotions. Each of the job titles except job title $$$1$$$ has only one possible promotion path, that is job title $$$i$$$ can be promoted to job title $$$P_i$$$ in exactly one year ($$$1 \leq P_i \lt i$$$). A job title is considered entry-level if no other job title promotes to it.
The company hasn't decided on the salary of each job title yet, but there are some restrictions. The company has a minimum wage of $$$L$$$ and a maximum wage of $$$H$$$. Every single entry-level job title has minimum wage salary. Any promotion will never decrease the salary. The company also implements a policy, "Wherever you are in the company ladder, the raise you will get from this year to the next year is never less than the raise you get from last year to this year."
In more formal words, you're tasked to construct an array $$$S$$$ (with $$$S_i$$$ being the salary of job title $$$i$$$) such that:
When considering every possible configuration, the company wonders, how much is the biggest possible value of the total salaries that satisfies these conditions (the biggest possible value of $$$S_1+S_2+\ldots+S_N$$$)?
The first line contains three integers $$$N$$$, $$$L$$$, and $$$H$$$ ($$$2 \leq N \leq 200\,000$$$; $$$1 \leq L \leq H \leq 10^{12}$$$) — the number of job titles, the minimum wage, and the maximum wage.
The second line contains $$$N-1$$$ integers $$$P_2, P_3, \ldots, P_N$$$ ($$$1 \leq P_i \lt i$$$) — the job title that each job title promotes to.
One number that represents the maximum sum of all salaries.
5 7 111 2 2 3
42
3 23 231 2
69
2 265 47611
5026
In the first example, a configuration of salaries for positions $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$ that produces the maximum sum is $$$11$$$, $$$9$$$, $$$8$$$, $$$7$$$, and $$$7$$$
