P15407 [NOISG 2026 Prelim] 米浴的数据结构课（暂无数据）

米浴正在上数据结构课！ 在数据结构课中，她学习了树的带权重心。 树的带权重心是这么定义的： 设 $a_i (a_i \ge 1)$ 表示 $i$ 的权值。点 $u$ 是树的重心当且仅当删去 $u$ 节点后，剩下的每个联通块的权值和都 $\le \frac{1}{2} \sum a_i$。 现在她的手上有一颗 $n$ 个节点的树，根节点是 1，点 $i$ 的点权为 $a_i$。 她想找到这棵树的带权重心，但是这太简单了。因此，她给自己加了 $q$ 次操作，每次操作有两种可能： - $1\ u\ v\ w$，表示给所有 $u$ 到 $v$ 路径上的节点的点权增加 $w$ - $2\ u\ w$，表示给所有 $u$ 的子树内的节点的点权增加 $w$ 在每次操作后，她都希望找到这棵树的所有带权重心。如果有多个，那么按照编号从小到大的顺序输出。

本题有多组数据。 第一行一个正整数 $T (1 \le T \le 10000)$ 表示数据组数 对于每组数据，第一行两个整数 $n, q (1 \le n, q \le 10^5)$ 接下来一行 $n$ 个整数，分别是 $a_1, a_2, \ldots, a_n (1 \le a_i \le 10^8)$ 接下来 $n-1$ 行，每行两个整数 $u_i, v_i$，表示树上的一条边 接下来 $q$ 行，第 $i$ 行第一个整数是 $op_i \in \{1, 2\}$ - $op_i = 1$，接下来三个整数 $u, v, w (1 \le u, v \le n, w \le 10^8)$ - $op_i = 2$，接下来两个整数 $u, w (1 \le u \le n, w \le 10^8)$ 保证 $\sum n, \sum q \le 10^5$，输入的树是一棵树。

对于每组数据，输出 $q$ 行，第 $i$ 行输出若干个整数，分别表示经过 $i$ 次操作后树的所有带权重心按照编号从小到大排序后的结果。

### 子任务 对于 100% 的数据，均满足 $1 \le T \le 10000, 1 \le \sum n, \sum q \le 10^5, 1 \le a_i, w \le 10^8$ |子任务编号|限制条件|分值| |:-:|:-:|:-:| |1|$\sum n, \sum q \le 1000$|20| |2|满足树是一条链|10| |3|满足树是菊花图|10| |4|满足树的形态和操作都是均匀随机生成的|20| |5|没有额外限制|40|