1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/***
题目：http://hihocoder.com/contest/hiho109/problem/1
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
There is a tower defense game with n levels(missions). The n levels form a tree whose root is level 1.
In the i-th level, you have to spend pi units of money buying towers and after the level, you can sell the towers so that you have qi units of money back.
Each level is played once. You can choose any order to complete all the levels, but the order should follow the following rules:
1: A level can be played when all its ancestors are completed.
2: The levels which form a subtree of the original tree should be completed consecutively in your order.
You want to know in which order of completion you can bring the minimum money before starting the first level.
输入
The first line contains one single integers, n - the number of levels. (1<=n<=10000)
The next n lines describes the levels. Each line contains 2 integers, pi and qi which are described in the statement. (0<=qi<=pi<=20000)
The next n-1 lines describes the tree. Each line contains 2 integers, ai and bi which means there is an edge between level ai and level bi.
For 30% of the data, n<=100.
For 60% of the data, n<=1000.
输出
Print one line with an single integer representing the minimum cost.
样例提示
There are two orders of completing all levels which are: 1234 and 1342.
In the order 1234, the minimum beginning money is 5.
In the order 1342, the minimum beginning money is 7.
1324 is not a valid order because level 3 and level 4 are not completed consecutively.
样例输入
4
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX