P2607 [ZJOI2008] Knights

The knights’ order of country Z is a powerful organization that gathers elites from all over the land. They rob the rich to help the poor and punish evil while promoting good, earning praise from all sectors of society. Recently, a terrible event occurred: the evil country Y launched an invasion against country Z. War flames stretch for five hundred li. Having enjoyed peace for hundreds of years, country Z could hardly resist the army of country Y. Thus, people pinned all their hopes on the knights’ order, as if awaiting the birth of a true dragon emperor to lead justice to defeat evil. The knights’ order certainly has the ability to defeat evil forces, but there are often conflicts among the knights. Each knight has exactly one knight he hates the most (and it is not himself), and he absolutely refuses to go on campaign together with the one he hates the most. War is raging, and people are suffering. It is urgent to organize a knights’ army to join the battle. The king assigns you a difficult task: choose a subset of knights to form an army such that no two selected knights are in conflict (i.e., there does not exist a knight who is selected together with the knight he hates the most), and such that this army has the maximum combat power. To describe combat power, we number the knights from $1$ to $n$, and assign each knight an estimated combat power. The combat power of an army is the sum of the combat power of all selected knights.

The first line contains an integer $n$, the number of knights. The next $n$ lines, in order, describe each knight’s combat power and the knight he hates the most. Specifically, for $i = 1, \dots, n$, line $i$ contains two integers $w_i$ and $h_i$, where $w_i$ is the combat power of knight $i$, and $h_i$ is the index of the knight he hates the most, with $1 \le h_i \le n$ and $h_i \ne i$.

Output one line containing a single integer, the maximum combat power of the army you select.

Constraints: - For $30\%$ of the testdata, $n \le 10$. - For $60\%$ of the testdata, $n \le 100$. - For $80\%$ of the testdata, $n \le 10^4$. - For $100\%$ of the testdata, $1 \le n \le 10^6$, and each knight’s combat power is a positive integer not greater than $10^6$. Translated by ChatGPT 5