#P17817. [ONTAK 2023]TAK

[ONTAK 2023]TAK

题目描述

给定一棵 nn 个顶点的树,每个顶点的度数至多为 33。顶点 ii 的兴趣值为 cic_i,第 ii 条边的权值为 wiw_i。

一条有方向的简单路径是有趣的,当且仅当沿路径经过的顶点兴趣值严格递增。路径的费用等于它经过的所有边权的乘积。单个顶点也视为一条有趣路径,其费用为 11。

依次处理 qq 次修改:

  • 1 x y:将顶点 xx 的兴趣值改为 yy;
  • 2 x y:将第 xx 条输入边的权值改为 yy。

每次修改后,求所有有趣路径的费用之和,答案对 998244353998244353 取模。

输入格式

第一行包含 n,qn,q。第二行包含 c1,…,cnc_1,\ldots,c_n。 接下来 n−1n-1 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,依次描述编号为 ii 的边。 接下来 qq 行,每行三个整数 ti,xi,yit_i,x_i,y_i,描述一次修改。

输出格式

输出 qq 行,每行一个整数,表示对应修改后的答案。不需要输出修改之前的答案。

数据范围

2≤n≤5000002\le n\le500000,1≤q≤1000001\le q\le100000,1≤ci,yi≤n1\le c_i,y_i\le n(点权修改),0≤wi,yi≤1060\le w_i,y_i\le10^6(边权修改)。所有顶点度数至多为 33。

样例

6 5
1 2 2 1 1 1
1 2 1
2 5 1
2 3 1
3 4 1
3 6 1
1 3 3
2 3 2
1 4 4
1 6 4
2 2 3
13
16
23
28
42