5361: Bookshop
内存限制：128 MB
时间限制：7.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
DreamGrid will go to the bookshop tomorrow. There are n books in the bookshop in total, labeled by 1,2,…,n, connected by n−1 bidirectional roads like a tree. Because DreamGrid is very rich, he will buy the books according to the strategy below:
- Select two books x and y.
- Walk from x to y along the shortest path on the tree, and check each book one by one, including the x-th book and the y-th book.
- For each book being checked now, if DreamGrid has enough money (not less than the book price), he'll buy the book and his money will be reduced by the price of the book. In case that his money is less than the price of the book being checked now, he will skip that book.
输入
The first line contains a single integer T (1≤T≤500), the number of test cases. For each test case:
The first line of the input contains two integers n and q (1≤n,q≤100000), denoting the number of books in the bookshop and the number of queries.
The second line contains n integers p1,p2,…,pn (1≤pi≤109), denoting the price of each book.
Each of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), denoting a bidirectional road between ui and vi. It is guaranteed that the roads form a tree.
In the next q lines, the i-th line contains three integers xi, yi and zi (1≤xi,yi≤n, 1≤zi≤109), describing the i-th query.
It is guaranteed that the sum of all n is at most 800000, and the sum of all q is at most 800000.
The first line of the input contains two integers n and q (1≤n,q≤100000), denoting the number of books in the bookshop and the number of queries.
The second line contains n integers p1,p2,…,pn (1≤pi≤109), denoting the price of each book.
Each of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), denoting a bidirectional road between ui and vi. It is guaranteed that the roads form a tree.
In the next q lines, the i-th line contains three integers xi, yi and zi (1≤xi,yi≤n, 1≤zi≤109), describing the i-th query.
It is guaranteed that the sum of all n is at most 800000, and the sum of all q is at most 800000.
输出
For each query, print a single line
containing an integer, denoting the amount of money DreamGrid will have
after he checking all the visited books.
样例输入 复制
1
5 5
5 2 7 4 6
1 2
1 3
2 4
2 5
4 5 10
5 4 10
4 5 12
5 3 12
3 5 11样例输出 复制
4
2
0
4
2