VM7WC '15 #6 Gold - Agriphilosophical Data Slaves

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

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

1 2
1 3
2 4
2 5
4 -5 -3 10 6

Sample Output



The agriculturality of each of the data slaves is as follows: 12, 11, -3, 10, 6. Therefore, the largest is 12.


  • 0
    aeternalis1  commented on Aug. 1, 2017, 2:38 p.m.

    Is my method plausible?

    With enough optimization, is it possible for my method to stay within time and memory limits?

    • 0
      Pleedoh  commented on Aug. 13, 2017, 11:29 p.m.

      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.

      • 0
        aeternalis1  commented on Aug. 14, 2017, 5:18 a.m.

        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.

  • 9
    kobortor  commented on Feb. 12, 2015, 7:01 p.m.

    Zihao Zhang obviously haven't learned recursion yet. That would lead to a stack overflow.

    • 1
      root  commented on May 18, 2017, 10:53 p.m.

      Zhang Zihao is a master of the philosophy of compiling code, simplifying the recursion into an infinite loop instead.

    • 11
      thorthugnasty  commented on Feb. 12, 2015, 10:59 p.m.

      Zihao Zhang no longer goes to Massey, the top programmer is now Leo Feng.

      • 10
        LeoF  commented on Aug. 15, 2017, 5:38 p.m. edit 2

        Having graduated Massey, I crown Henning Jiang the new top programmer.