2711: 2025AHCPC - 决策路径

         在决策树模型中,   每个节点代表一个决策点,   每条边代表一个可能的决策路径,   边上的权重表示选择该路径的概率权重.   现在你需要实现一个数据结构,   能够高效地计算从根节点到任意指定节点的路径概率,   同时支持动态修改边的权重.

         给定一棵有根决策树,   包括 $n$ 个节点,   编号为 $1$ 到 $n$,   其中 $1$ 号节点为根节点.   每个非叶子节点都有若干子节点,   每条从父结点到子节点的边都有一个初始权重.   从父结点到各个子节点的选择概率由这些权重决定   (权重越大,   被选中的概率越高).

         你需要实现以下两种操作:

         $1.$   修改某条边的权重   (保证该边存在)

         $2.$   查询从根节点到某个指定节点的路径概率   $($在模 $998244353$ 下的值,   定义有理数的模为:   若概率值等于 $\frac {Q}{P} ,$ 其中 $P$ 和 $Q$ 为整数且 $Q$ 不等于 $0$,   则在模 $MOD$ 下的结果为:   $P \times Q$ 的逆元,   其中 $Q$ 的逆元满足:   $Q \times Q$ 的逆元 $\equiv 1 \ mod \ MOD)$

         路径概率定义为从根节点出发,   沿着路经依次选择对应子节点的概率的乘积.

         第一行包含两个整数 $n$ 和 $q$,   表示树的节点数和操作数.

         接下来的 $ n - 1$ 行,   每行描述一个节点   (除根结点外)   的信息,   格式为: $p \ w \ u$表示节点 $u$ 的父节点是 $p$,   初始边权重为 $w$.

         接下来 $q$ 行,   每行一个操作:

         $1 \ u \ w:$   将节点 $u$ 到其父节点边的权重修改为 $w$.

         $2 \ u:$   查询从根节点到节点 $u$ 的路径概率   (模 $998244353$)

5 5
1 1 2
1 2 3
2 1 4
2 3 5
2 4
1 4 5
2 4
1 2 4
2 5

582309206
457528662
748683265