M. Closed Paths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes and a fixed even integer $$$k$$$. Node $$$i$$$ has weight $$$a_i$$$.

A closed path on a tree is a path that starts and ends at the same node. A closed path may visit the same node multiple times. A closed path of length $$$k$$$ that starts at node $$$1$$$ can be written as $$$x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{k+1}$$$, where:

  • $$$x_1 = x_{k+1} = 1$$$;
  • node $$$x_i$$$ and $$$x_{i+1}$$$ are adjacent on the tree.

The score of the closed path $$$x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{k+1}$$$ is defined as $$$\sum_{i=1}^{k+1} a_{x_i}$$$.

You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you are given two numbers $$$p_i$$$ and $$$v_i$$$, which means you should update the value of $$$a_{p_i}$$$ to $$$v_i$$$. After the update, you need to find the score of a closed path of length $$$k$$$ starting at node $$$1$$$ that has the maximum possible score. Note that the updates are permanent.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2.5 \cdot 10^4$$$), the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq k \leq 10^9$$$), the number of nodes in the tree and the length of the closed path, respectively. It is guaranteed that $$$k$$$ is even.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the initial weights of the nodes.
  • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), representing an edge between nodes $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that the given input forms a tree.
  • The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$), the number of queries.
  • The next $$$q$$$ lines each contain two integers $$$p_i$$$ and $$$v_i$$$ ($$$1 \leq p_i \leq n$$$, $$$1 \leq v_i \leq 10^9$$$), indicating that the value of $$$a_{p_i}$$$ should be updated to $$$v_i$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ respectively.

Output

For each query, output a single integer in a new line  — the maximum score of a closed path of length $$$k$$$ starting at node $$$1$$$ after applying the update.

Example
Input
2
4 6
1 4 3 1
1 2
1 3
4 3
2
2 3
4 2
2 1000000000
1 1
1 2
4
1 1000000000
2 1000000000
1 1
2 1
Output
13
15
500000001500000000
1000000001000000000
500000000500000001
1000000001
Note

In the first query of the first test case, $$$a=[1,3,3,1]$$$ and $$$k=6$$$. One of the possible closed paths of length $$$k$$$ that starts at node $$$1$$$ is $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 1$$$. The score of this closed path is $$$13$$$.

It can be proven that $$$13$$$ is the maximum possible score of a closed path.

In the first query of the first test case, $$$a=[1,3,3,2]$$$ and $$$k=6$$$. One of the possible closed paths of length $$$k$$$ that starts at node $$$1$$$ is $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 1$$$. The score of this closed path is $$$15$$$.

It can be proven that $$$15$$$ is the maximum possible score of a closed path.