格兰之森¶
- 参考时间限制：1.0 秒（评测环境与性能）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 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¶
输入¶
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
输出¶
1
5
3
样例 2¶
输入¶
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
输出¶
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<n\) ，\(1\le q\le10000\) ，\(|c_i|\le10000\) .操作 1、2 中 \(|c|\le10000\) ，操作 3、4 中 \(|d|\le100000000\) .节点编号在 \(1,\ldots,n\) 内；边构成森林，每次操作的两端连通。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |