In philosophy class, you are given a set of data slaves numbered from 
~1~ to 
~N~ 
~(1 \le N \le 400\,000)~ who each must manually type out test data for the 7 Week Challenge (yes, this is really how the test data is made). The 
~i^\text{th}~ 
~(2 \le i \le N)~ data slave must type out 
~c_i~ 
~(-1000 \le c_i \le 1000)~ characters before sending all his work to his superior data slave. The superior data slave will have a supervisor with a lower identifying number. The exception to this is the data slave numbered ~1~ (Leo Feng), who has no superior. Note that the data slaves are unintelligent and may sometimes delete characters accidentally, when 
~c_i < 0~. Define the agriculturality of a data slave to be the total number of characters that he types as well as those that are typed by those who work under him (accounting for those deleted as well). In other words, the agriculturality of a data slave is the sum of the work done in the subtree rooted at that slave. Considering all data slaves, find the maximum agriculturality of a single data slave. You plan to promote this slave, which you believe may be useful to solving the "What is the meaning of life" problem.
For inspiration,
"The meaning of life is to find the meaning of life."
~ Philosopher Zihao Zhang 2014.
Input Specification
The first line will have the single integer ~N~.
Each of the following 
~N-1~ lines will contain two space separated integers, where the first number will correspond to the data slave who is the superior of the data slave with the second number. The next line will contain ~N~ space-separated integers, representing the number of characters each data slave types, in order.
Output Specification
Print the maximum agriculturality of a single slave.
Sample Input
5
1 2
1 3
2 4
2 5
4 -5 -3 10 6
Sample Output
12
Explanation
The agriculturality of each of the data slaves is as follows:
12, 11, -3, 10, 6. Therefore, the largest is 12.
Comments
Is my method plausible?
With enough optimization, is it possible for my method to stay within time and memory limits?
Just use some recursion from the root (1) to define the total agriculturality of each slave. Again, I don't know much Python but it seems you're doing some unecessary searching and operating.
I'd already tried using recursion before (granted, with a wrong implementation), and I revisited such a method with no success. I ended up either TLE'ing or MLE'ing cases 8, 9 and 10.
Zihao Zhang obviously haven't learned recursion yet. That would lead to a stack overflow.
Zhang Zihao is a master of the philosophy of compiling code, simplifying the recursion into an infinite loop instead.
Zihao Zhang no longer goes to Massey, the top programmer is now Leo Feng.
Having graduated Massey, I crown Henning Jiang the new top programmer.