#P8. 【USTCPC2024】F. 楼高统计

    ID: 162 Type: Default 2000ms 256MiB

【USTCPC2024】F. 楼高统计

小仓鼠李华去的小学是一所发展飞快的学校。学校有 nn 个路口与 n1n - 1 条连接两个路口的道路,且每两个路口之间都可以通过道路直接或间接到达。每个路口都建有一栋楼,第 ii 个路口的楼高为 hih_i。李华经常会从其中一个路口走到另一个路口,在走的过程中,它会记录下所能看到的每栋楼的高度,且不会重复记录同一栋楼

当李华走到路口 vv 时,它能看到 vv 以及所有与 vv 相邻路口(即通过一条路直接连接的路口)的楼。李华对校园很熟悉,所以不会绕路,也就是说,对于每一对路口 (u,v)(u, v),它从 uuvv 的路线都是唯一的。每次李华结束行程后,它都想知道记下来的所有楼高度的均值和方差。

提示:kk 个数 a1,a2,,aka_1, a_2, \dots, a_k 的均值和方差为:

$$E(a) = 1/k \sum_{i=1}^k a_i\\ \text{Var}(a) = 1/k \sum_{i = 1}^k (a_i - E(a))^2 $$

另外,学校也在发展,包括以下两类事件:

  1. 取一对点 (u,v)(u, v),将 uuvv 的路径上(包含端点)所有的楼进行加盖操作,其高度均增加 hh
  2. 取一对点 (u,v)(u, v),将 uuvv 的路径上(包含端点)所有高度超过 HH 的楼进行降沉操作,通过挖地将低楼层降沉至地下,使楼高减小至 HH

现在给定学校发展和李华行程发生的顺序,请你求出每次行程记录的楼的均值和方差。李华非常讨厌小数,所以请将答案对 998244353 取模。具体来说,若答案可以表示为 pq\frac pq,请输出 pq1p \cdot q^{-1} 对 998244353 取模的值,其中 q1q1(mod998244353)q^{-1} \cdot q \equiv 1 (\bmod 998244353)

Input

输入第一行:两个整数 n,mn, m1n105,1m1051 \le n \le 10^5, 1 \le m \le 10^5),表示学校的路口个数,以及发生的事件数量。

第二行:nn 个整数 h1,h2,,hnh_1, h_2, \dots, h_n1hi1081 \le h_i \le 10^8),表示初始时每栋楼的高度。

接下来 n1n - 1 行:每行两个整数 u,vu, v1u,vn1 \le u, v \le n),表示每条道路。

接下来 mm 行:每行描述一个事件(1u,vn1 \le u, v \le n),格式如下:

  • 1 uu vv hh:第 11 类学校发展事件,1h50001 \le h \le 5000
  • 2 uu vv HH:第 22 类学校发展事件,1H5×1081 \le H \le 5 \times 10^8
  • 3 uu vv:李华行程事件,从 uu 走到 vv

Output

输出若干行:对于每次行程,输出李华希望得到的均值和方差,对 998244353 取模。

Examples

Sample Input 1

7 5
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
3 1 7
1 3 6 5
3 4 7
2 4 5 1
3 1 4

Sample Output 1

399297745 878455036
570425350 40744678
199648873 718735942

样例中,学校地图如下:

初始时各楼高度分别为 1 2 3 4 5 6 7,李华从路口 1 走到路口 7,经过的路口为 1 3 7,看到的楼的编号为 1 2 3 6 7,高度分别为 1 2 3 6 7,均值为 195\frac{19}5,方差为 13425\frac{134}{25}

学校第一次发展,路口 3 到路口 6 的路径上所有的楼高增加 5,各楼高度变成 1 2 8 4 5 11 7,李华从路口 4 走到路口 7,经过的路口为 4 2 1 3 7,能看到所有的楼,均值为 387\frac{38}7,方差为 51649\frac{516}{49}

学校第二次发展,路口 4 到路口 5 的路径上所有高度超过 1 的楼进行降沉操作,各楼高度变成 1 1 8 1 1 11 7,李华从路口 1 走到路口 4,经过的路口为 1 2 4,看到的楼的编号为 1 2 3 4 5,高度分别为 1 1 8 1 1,均值为 125\frac{12}5,方差为 19625\frac{196}{25}

Related

In following contests:

USTCPC2025 测试赛