9132: Average
内存限制：256 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
You are given a tree with n nodes. Every node has its value au. The value of a path(u, v) on the tree is equal to
where path(u, v) is the shortest path from u to v, len(u, v) means the number of nodes in path(u, v).
You have to answer questions like what is the maximum possible value of a path with length greater than or equal to k. Unfortunately, the value of nodes will increase. So you need to answer the question after each change.
where path(u, v) is the shortest path from u to v, len(u, v) means the number of nodes in path(u, v).
You have to answer questions like what is the maximum possible value of a path with length greater than or equal to k. Unfortunately, the value of nodes will increase. So you need to answer the question after each change.
输入格式
Each test contains multiple test cases. The first line contains an integer T(1 ≤ T ≤ 105), indicating the number of test cases. The description of test cases follows.
The first line contains two integers n,k (1 ≤ n ≤ 105, 1 ≤ k ≤ 30).
The second line contains n integers ai(1 ≤ ai ≤ 109).
The following n − 1 lines contains 2 integers ui and vi (1 ≤ ui, vi ≤ n, ui ̸= vi), indicating an edge between vertices ui and vi. It is guaranteed that the given edges form a tree.
The next line contains a integer q (1 ≤ q ≤ 104).
The following n − 1 lines contains 2 integers ui, x (1 ≤ ui ≤ n, 1 ≤ x ≤ 109), indicating that the value of node ui will increase x.
It is guaranteed that the sum of n over all test cases does not exceed 2.5 × 105, and the sum of q over all test cases does not exceed 2.5 × 104.
The first line contains two integers n,k (1 ≤ n ≤ 105, 1 ≤ k ≤ 30).
The second line contains n integers ai(1 ≤ ai ≤ 109).
The following n − 1 lines contains 2 integers ui and vi (1 ≤ ui, vi ≤ n, ui ̸= vi), indicating an edge between vertices ui and vi. It is guaranteed that the given edges form a tree.
The next line contains a integer q (1 ≤ q ≤ 104).
The following n − 1 lines contains 2 integers ui, x (1 ≤ ui ≤ n, 1 ≤ x ≤ 109), indicating that the value of node ui will increase x.
It is guaranteed that the sum of n over all test cases does not exceed 2.5 × 105, and the sum of q over all test cases does not exceed 2.5 × 104.
输出格式
Output the answer A/B, indicating the value is A/B and gcd(A, B) = 1. If no such path, output "0/1".
输入样例 复制
2
6 2
6 16 6 15 5 4
1 2
2 3
2 4
2 5
4 6
2
1 4
3 5
14 1
12 19 9 17 9 10 11 18 9 19 10 14 18 8
1 2
2 3
1 4
1 5
4 6
2 7
7 8
8 9
6 10
6 11
1 12
11 13
3 14
5
10 3
2 8
7 9
5 6
2 1000000000输出样例 复制
31/2
31/2
22/1
27/1
27/1
27/1
1000000027/1