提示: 欢迎访问OurACM平台。
Problem 1615 Hero's RP

Accept: 136    Submit: 282
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Recently, our fortunate hero gains a lot of money. So he decides to feast people in order to accumulate RP(short for Ren Pin). He lists out people’s name on a paper. The very nosy tzw finds a very strange thing: These n people forms a network of tree struction, the father node is the direct leader of the son node, feast each person can get a certain amount of RP values, but if a person and his direct leader are both invited, then he will feel pressure, --! So the RP value which hero can get from this person will reduce. And if he has the honor to be invited with indirect leaders (it means the node’s father node …’s father node)but without direct leader, his RP value remain the same, Finally our hero decides only invite part of people from these people to gain the maximum value of RP. ->_<-

Input

There are multiple test cases.

The first line of each test case contains a positive integer n(1≤n≤10000) ,indicating that there are n people. followed by n lines , each line contains a string people_name and an positive integer num(the length of each person’s name will not exceed 10). indicting that if people_name was invited, hero will get num RP values. Then n-1 lines was followed, each line contains two strings people_name_a and people_name_b and a positive integer num, indicting that people_name_a is the direct leader of people_name_b, and if they are both invited, hero will lose num RP values from people_name_b. (We guarantee the relationship is a tree, and the n+2th line’s people_name_a for each test case is the root).

Output

For each test case, print a line contains an integer, indicting the maximum RP values that the hero can get.

Sample Input

6 cy 100 roam 50 tzw 80 tqm 70 wjn 60 tcx 90 cy roam 80 cy tzw 80 tzw tqm 80 roam wjn 80 roam tcx 80

Sample Output

320

Source

FOJ月赛-2008年6月 -- Heroes Happen Here

Submit  Back  Status  Discuss