Devu, his friends and birthday gifts
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
You might have realized up to now that some of the Devu's friend are really weird. It is Devu's 22nd birthday today. His friends are coming to his home for his birthday party. Some of his friends are so shameless that instead of giving him a gift, they even ask gifts from him.
Devu has n friends. He wants to invite some of his friends in the party. Devu knows beforehand that ith friend will give a gift of ri rupees. If ri is positive, then it means that they will give a gift of |ri| rupees to Devu, otherwise it means that they want to receive a gift of|ri| rupees from Devu.
Devu's friend are really weird and they keep conditions before Devu like this : "If you invite me, you should also invite my best friend too". For ith person, you are given an integer fi denoting his best friend. It means that if Devu invites ith person, then he has to invite person fi too. Please note that best friend relationship is not bi-directional i.e. it is not necessary that if A is best friend of B, then B should be best friend of A.
You have to help Devu in choosing an optimal set of friends to invite so that the total amount of money he receives in gifts is maximum. Devu can also choose to not to invite anyone at all. Find out the maximum total amount of money Devu can have.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- First line of each test case will contain a single integer n denoting total number of friends of Devu.
- Second line contains n space separated integers denoting array f which describes best friend of ith person.
- Third line contains n space separated integers denoting array r as stated in the problem.
- For each test case, print a single line containing maximum amount of rupees he can have in the end.
- 1 ≤ T ≤ 105
- 2 ≤ n ≤ 105
- -109 ≤ ri ≤ 109
- 1 ≤ fi ≤ n
- fi != i
- Sum of n over all the test cases will be less than or equal to 106
Input: 4 2 2 1 3 5 2 2 1 -3 5 3 2 3 2 -2 2 4 3 2 3 2 -1 -2 -3 Output: 8 2 6 0
Example case 1. Both his friends are giving him gifts. So he will invite both of them to the party and will collect 8 rupees from the gifts received.
Example case 2. He invites both of the friends and total rupees collected will be 2 rupees. He can not invite 2nd friend only, because 1st person is a best friend of 2nd person and he must be invited too if 2nd friend is invited.
Example case 3. He will invite second and third of his friends. So total rupees collected will be 6 rupees.
Example case 4. In this case, all of his friends want to receive gifts from Devu. It is better for him to invite none. So he will receive total 0 rupees.
|Tags||admin2, basic-graph, cook58, easy|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.