53 - ZJUPC ZyXel Cup 2006 - 1006
The military base has built a communication network. The network consists of several communication terminals which are connected by cables. Each terminal can talk with its direct neighbors, but it can not talk with three or more neighbors at any time. So terminals on the same "communication line" can talk with each other concurrently, but they can not communicate with other terminals in the network at the same time. The design of the network has a very serious problem. When one terminal wants to change its communication targets, the whole network will become unavailable until it is finished. For example, suppose that terminal A is talking with terminal C through a intermediate terminal B. When other two terminals D and E request for the help of terminal B, terminal B should stop communication with terminal A and C, and be reset to talk with terminal D and E. Before the communication with A to C is finished, any terminal in the network can not communicate with others, even if they have no relation with terminal A to C. Luckily, when multiple terminals are reset together, the network stalls only once. Because of this serious issue, leaders decide that terminals may only be reset in the mid-night.
Now we know that the topology of the network is just a tree. There is only one communication path between any two terminals. You have received a lot of communication applications. Suppose that each application has its estimated value and the network stall caused by a terminal reset has its estimated cost. You should make a plan maximizing the value. A plan's value is the sum of all accepted applications' values minus the sum of all resets' costs. Note that the first initialzation of the whole network is free.
The input consists of multiple test cases. Each test case starts with a positive integers N which is the number of terminals in the network. The following N-1 lines each contains two distinct integers representing terminals connected by the cable. Terminals are always numbered from 1. After then, there is an integer M which indicates the number of applications. Each application consists of 4 positive integers D, A, B and V. D is the planned date of communication, represented by the number of days after today. A and B are terminals need to communicate on that day. V is its estimated value. The test case ends with a positive integer C which is the estimated cost of a network stall.
There are no more than 50 terminals or applications in test cases.
For each test case, you should output the value of your plan on a single line.
5 1 2 1 3 2 4 2 5 5 1 1 2 5 1 1 3 2 2 2 3 3 2 4 5 1 3 4 1 2 10