Replica Placement#2189
Topsky wants to build a content delivery network. It consists of an origin server and several mirror servers, as shown in Figure . The original data is stored on the origin server (the root in Figure ), while replicas may be placed on some of the mirror servers (nodes and in Figure ). When a node issues a request for data, it tries to locate the data as described below.
Check if there is a replica at its own location. If yes, the request is served. Otherwise, move to step .
Forward the request to its parent, and let its parent perform step .
The cost of fulfilling the request is defined as the sum of the weights of the edges along the path. If does not exceed the upper bound , the retrieval cost is considered acceptable. Topsky assumes a nonnegative storage cost , which is the cost of storing the data at node . Note that the origin server is special: the storage cost for the origin server is .
Topsky wants to place the replicas so that the retrieval cost for all nodes is acceptable and the total storage cost is minimized.
The first line contains an integer (1 \leq t \leq 20), the number of test cases. Each test case starts with an integer (1 \leq n \leq 1000), the number of servers. Then lines follow. Each line contains four integers: F_v (0 \leq F_v \leq n), Q_v, S_v, and W_v (0 \leq Q_v, S_v, W_v \leq 10^5). In line (1 \leq i \leq n), F_v is the parent of node (if F_v is , then node is the origin server, Q_v, S_v, and W_v for this node are , , and respectively); Q_v is the upper bound on retrieval cost, S_v is the storage cost at node , and W_v is the weight of the edge between node and F_v.
For each test case, output the minimal total storage cost in a separate line.
Example 1