
120  ZOJ Monthly, September 2012  F
There are n individuals(2 <= n <= 30000). Everyone has one or more friends. And everyone can contact all people by friendrelation. If two persons aren't friends, they also can contact by their friends. Each pair of friends have a friendship value a_{i}(1 <= a_{i} <= 50000). Firstly, you will relieve some friendrelation. The rest of the friendrelation is the social net. The net is unique in all test cases. In this net, everyone can contact all people by rest friendrelation. The net has a minimum number of friendrelation. And the net has maximum sum of friendship value. We want to get the maximum sum. Secondly, everyone has an angry value b_{i}(1 <= b_{i} <= 100000). We have q operations(1 <= q <= 30000): Person X wants to contact person Y, this operation merely has one sequence which describes the process. The sequence consists of persons' angry value. The persons are on the process. We suppose the sequence is c_{1}, c_{2}, c_{3}, ... ,c_{i}. Here c_{i} means the angry value of the ith people in the sequence. We attempt to find the maximum c_{k}c_{j} (c_{k} >= c_{j}, j <= k). Example: The sequence is 3(X), 4, 5, 6, 7, 5, 9, 4, 11(Y). The maximum c_{k}c_{j} is 113=8. The sequence is 3(X), 4, 5, 6, 7, 5, 9, 2, 11(Y). The maximum c_{k}c_{j} is 112=9. The sequence is 3(X), 10, 2, 5(Y). The maximum c_{k}c_{j} is 103=7. InputThe input contains multiple test cases. Each test case begins with a line containing a single integer n. The following line contains n integers bi. The subsequent line describe the number of relations m(n <= m <= 50000). The next m lines contain the information about relations: x, y, ai. Their friendship value is ai. Afterward gives q. The next q lines contain the operations: x, y. person X wants to contact person Y. OutputFor each case, print maximum sum of friendship value of the net on the first line. The next q lines contain the answers of every operations. Sample Input6 3 5 1 7 3 5 7 1 2 5 1 3 6 2 4 7 2 5 8 3 6 9 4 5 1 5 6 2 5 6 1 6 2 6 3 6 4 6 5 Sample Output35 2 4 0 6 4 Author: ZHANG, Chi 