#P17817. [ONTAK 2023]TAK
[ONTAK 2023]TAK
题目描述
给定一棵 个顶点的树,每个顶点的度数至多为 。顶点 的兴趣值为 ,第 条边的权值为 。
一条有方向的简单路径是有趣的,当且仅当沿路径经过的顶点兴趣值严格递增。路径的费用等于它经过的所有边权的乘积。单个顶点也视为一条有趣路径,其费用为 。
依次处理 次修改:
1 x y:将顶点 的兴趣值改为 ;2 x y:将第 条输入边的权值改为 。
每次修改后,求所有有趣路径的费用之和,答案对 取模。
输入格式
第一行包含 。第二行包含 。 接下来 行,每行三个整数 ,依次描述编号为 的边。 接下来 行,每行三个整数 ,描述一次修改。
输出格式
输出 行,每行一个整数,表示对应修改后的答案。不需要输出修改之前的答案。
数据范围
,,(点权修改),(边权修改)。所有顶点度数至多为 。
样例
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