Problem Description

Miyu is taking a data structures class.

In the class, she learned about the weighted centroid of a tree.

The weighted centroid of a tree is defined as follows:

Let $a_i (a_i \ge 1)$ denote the weight of node $i$. A node $u$ is a centroid of the tree if and only if, after deleting node $u$, for every remaining connected component, the sum of weights in that component is $\le \frac{1}{2} \sum a_i$.

Now she has a tree with $n$ nodes, rooted at node 1, and the node weight of node $i$ is $a_i$.

She wants to find the weighted centroid of this tree, but that is too easy. So she adds $q$ operations for herself, and each operation is one of the following two types:

• $1\ u\ v\ w$: Increase the node weights of all nodes on the path from $u$ to $v$ by $w$.
• $2\ u\ w$: Increase the node weights of all nodes in the subtree of $u$ by $w$.

After each operation, she wants to find all weighted centroids of the tree. If there are multiple, output them in increasing order of node indices.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T (1 \le T \le 10000)$, denoting the number of test cases.

For each test case, the first line contains two integers $n, q (1 \le n, q \le 10^5)$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n (1 \le a_i \le 10^8)$.

The next $n - 1$ lines each contain two integers $u_i, v_i$, denoting an edge in the tree.

The next $q$ lines describe the operations. In the $i$-th line, the first integer is $op_i \in \{1, 2\}$.

• If $op_i = 1$, then three integers $u, v, w (1 \le u, v \le n, w \le 10^8)$ follow.
• If $op_i = 2$, then two integers $u, w (1 \le u \le n, w \le 10^8)$ follow.

It is guaranteed that $\sum n, \sum q \le 10^5$, and the input graph is a tree.

Output Format

For each test case, output $q$ lines. In the $i$-th line, output some integers, which are all weighted centroids of the tree after the $i$-th operation, sorted in increasing order of node indices.

1
5 3
1 1 1 1 1
1 2
1 3
3 4
3 5
1 1 1 1
1 1 1 1
2 3 5

1 3
1
3

Hint

Subtasks

For 100% of the testdata, it holds that

$1 \le T \le 10000, 1 \le \sum n, \sum q \le 10^5, 1 \le a_i, w \le 10^8$

Translated by ChatGPT 5