# 格兰之森 - 参考时间限制：**1.0 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。 - 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。 - 内存限制：**128 MB**。 ## 背景故事 格兰之森的大火之后，精灵们正在修复森林中的魔法阵。魔法阵的连接构成一片森林，每个节点保存一份能量。修复工作会沿路径增加或重设能量，也需要统计达到指定能量门槛的节点。 ## 形式化问题描述 给定一片含 $n$ 个节点、$m$ 条无向边的森林，节点编号为 $1,\ldots,n$ ，节点 $i$ 的初始权值为 $c_i$ . 依次执行 $q$ 次操作，每次给出的节点 $a,b$ 保证在同一棵树中。路径均为两点间唯一的简单路径，**包含两个端点**；当 $a=b$ 时只包含一个节点。 - `1 a b c` ：把路径上每个节点的当前权值增加 $c$ . - `2 a b c` ：把路径上每个节点的当前权值设为 $c$ . - `3 a b d` ：输出路径上当前权值大于或等于 $d$ 的节点数量。 - `4 a b d` ：输出这些节点的当前权值之和。 增加量、权值和门槛都可以为负。没有满足门槛的节点时，数量和权值之和均为 $0$ . ## 输入格式 第一行三个整数 $n,m,q$ .第二行 $n$ 个整数 $c_1,\ldots,c_n$ . 接下来 $m$ 行，每行两个整数，表示一条无向边的两个端点。接下来 $q$ 行，每行四个整数，表示一个操作。 ## 输出格式 对每个操作 3 或操作 4，按出现顺序输出一行整数。 ## 样例 1 ### 输入 ```text 3 2 5 5 5 2 2 1 3 2 3 2 3 4 2 2 3 0 4 1 3 4 1 1 3 5 3 1 3 5 ``` ### 输出 ```text 1 5 3 ``` ## 样例 2 ### 输入 ```text 4 2 7 -2 0 3 -4 1 2 2 3 4 1 3 -2 2 1 3 -3 1 2 3 5 3 1 3 2 4 1 3 -10 4 4 4 -4 3 4 4 0 ``` ### 输出 ```text 1 2 1 -4 0 ``` ## 样例解释 样例 1 中，首次查询的路径权值为 $5,2$ ，只有一个权值不小于 $4$ .设值后，整条 $1\to3$ 路径的权值为 $5,0,0$ ，门槛为 $4$ 的权值之和为 $5$ .最后一次加法把它们变为 $10,5,5$ . 样例 2 包含一个孤立节点。设值和加法后，节点 $1,2,3$ 的权值为 $-3,2,2$ ，所以门槛为 $-10$ 的权值之和为 $1$ ；节点 $4$ 的权值之和可以是 $-4$ . ## 数据范围与保证 对 100% 的数据：$1\le n\le500000$ ，$0\le m