ABHISHEK AND HIS POKEMON

3.1

9 votes
Problem

Abhishek and Ron were on their way to the pokemon league when Ron asked Abhishek what is the order in which he will use his pokemons in the tournament. Since Abhishek has N pokemons, he got confused and asked for your help.

To decide which pokemon are stronger than others, he held N-1 pokemon battles, and obtained a tree representing the relationship between strengths of pokemon, every pokemon except pokemon 1  was defeated exactly once.

Note : if A beats B and B beats C it implies that A beats C.

Also, Abhishek likes some pokemon more than others and wants to use them before others. Now he asks you for an ordering of the pokemons such that the stronger pokemon are to the left of weaker pokemon, since multiple such orderings are possible , he wants you to minimise the number of pairs where a non favourite pokemon comes before a favourite pokemon.

 

UPDATE  : Custom input output is allowed in this question.

 

Input : 

N,  Number of pokemon Abhishek has 

X1 X2 X3 . . . .. . XN , Xi denotes whether ith pokemon is F(Favourite) or N (Not favourite).

W2 W3 W4 . . . . . WN ,  Wi is the pokemon that defeated the ith pokemon ( Pokemon 1 is the 

strongest and is undefeated).

 

Constraints:

1 <= N <= 2*10^5

 

Output : 

Print one integer the minimum number of pairs of pokemon where a non favourite pokemon comes before a favourite pokemon, and a stronger pokemon is always to the left of a weaker pokemon.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Power relationships : 

Power(1) > Power(2) > Power(4)

Power(1) > Power(3) > Power(5)

A valid ordering would be, 

1 2 4 3 5 

N F F N F 

We can find 4 (N , F) pairs ie. { (1, 2) , (1,4) , (1,5) , (3,5) }

Editor Image

?