主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem J: 2025AHCPC_J决策路径
上一题
正确率: $39.13\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$128$ 兆字节/Megabyte(s)
提交总数
$23$
正确数量
$9$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
单击选择分类:
Description
<p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 在决策树模型中, 每个节点代表一个决策点, 每条边代表一个可能的决策路径, 边上的权重表示选择该路径的概率权重. 现在你需要实现一个数据结构, 能够高效地计算从根节点到任意指定节点的路径概率, 同时支持动态修改边的权重.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span class="md" style="color:#000000;"> 给定一棵有根决策树, 包括 n 个节点, 编号为 1 到 n, 其中 1 号节点为根节点. 每个非叶子节点都有若干子节点, 每条从父结点到子节点的边都有一个初始权重. 从父结点到各个子节点的选择概率由这些权重决定 (权重越大, 被选中的概率越高).</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span class="md" style="color:#000000;"> 你需要实现以下两种操作:</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span class="md" style="color:#000000;"> 1. 修改某条边的权重 (保证该边存在)</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span class="md" style="color:#000000;"><span style="color:#000000;"> 2. 查询从根节点到某个指定节点的路径概率 (在模 998244353 下的值, 定义有理数的模为: 若概率值等于 QP, 其中 P 和 Q 为整数且 Q 不等于 0, 则在模 MOD 下的结果为: P×Q 的逆元, 其中 Q 的逆元满足: Q×Q 的逆元 ≡1 mod MOD)</span></span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span class="md" style="color:#000000;"> 路径概率定义为从根节点出发, 沿着路经依次选择对应子节点的概率的乘积.</span> </p>
Input
<p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 第一行包含两个整数 n 和 q, 表示树的节点数和操作数.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 接下来的 n−1 行, 每行描述一个节点 (除根结点外) 的信息, 格式为: p w u表示节点 u 的父节点是 p, 初始边权重为 w.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 接下来 q 行, 每行一个操作:</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 1 u w: 将节点 u 到其父节点边的权重修改为 w.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 2 u: 查询从根节点到节点 u 的路径概率 (模 998244353)</span> </p>
Output
<span style="color:#000000;font-family:Google_sans;font-size:17px;"> 对于每个查询操作, 输出一行包含一个整数, 表示路径概率在模 </span><span style="color:#000000;">998244353</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 下的值.</span><span style="color:#000000;"></span>
Sample Input
复制
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
Sample Output
复制
582309206 457528662 748683265
AOJ
Please Login