P3408 Love

Xiao A fell in love with Xiao B!!! However, Xiao A is too weak compared to Xiao B, so she would certainly not agree to Xiao A’s request. After Xiao A’s persistent pursuit, Xiao B set the following conditions: - Xiao B has $n$ subordinates (excluding Xiao B) forming a tree structure. Xiao B is at the top, and everyone else has exactly one direct superior. - Xiao B is numbered $0$, and others are numbered $1 \sim n$. - For the $i$-th person: if this person has no subordinates, then Xiao A can give them $A_i$ yuan, after which they will write a letter to their direct superior, stating that Xiao A is confessing to Xiao B. - If at least a proportion of $\dfrac{A_i}{T}$ among their direct subordinates write letters stating that Xiao A is confessing to Xiao B, then they will also write a letter to their direct superior. - If at least a proportion of $\dfrac{C}{T}$ among Xiao B’s direct subordinates write letters stating that Xiao A is confessing to Xiao B, then she will agree to Xiao A’s request. Please determine the minimal total amount of money Xiao A needs to pay to make Xiao B accept Xiao A’s confession.

The first line contains three integers $n, T, C$. Then follow $n$ lines. The $i$-th line contains two integers $B_i, A_i$, where $B_i$ is the direct superior of $i$, and it is guaranteed that $B_i < i$.

Output the minimal total amount of money needed.

- For $20\%$ of the testdata, the number of people without direct subordinates $\le 15$. - For $40\%$ of the testdata, $n \le 2000$. - Additionally, for $10\%$ of the testdata, $B_i = 0$. - Additionally, for $10\%$ of the testdata, $C = 1$ and for people with direct subordinates $T / A_i > n$. - Additionally, for $10\%$ of the testdata, $B_i = i - 1$. - For $100\%$ of the testdata, $1 \le n \le 500000$, $1 \le T \le {10}^9$, $B_i < i$, $1 \le A_i \le T$. Translated by ChatGPT 5