| Time Limit | 1 秒/Second(s) | Memory Limit | 128 兆字节/Megabyte(s) |
| 提交总数 | 0 | 正确数量 | 0 |
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
在决策树模型中, 每个节点代表一个决策点, 每条边代表一个可能的决策路径, 边上的权重表示选择该路径的概率权重. 现在你需要实现一个数据结构, 能够高效地计算从根节点到任意指定节点的路径概率, 同时支持动态修改边的权重.
给定一棵有根决策树, 包括 n 个节点, 编号为 1 到 n, 其中 1 号节点为根节点. 每个非叶子节点都有若干子节点, 每条从父结点到子节点的边都有一个初始权重. 从父结点到各个子节点的选择概率由这些权重决定 (权重越大, 被选中的概率越高).
你需要实现以下两种操作:
1. 修改某条边的权重 (保证该边存在)
2. 查询从根节点到某个指定节点的路径概率 (在模 998244353 下的值, 定义有理数的模为: 若概率值等于 QP, 其中 P 和 Q 为整数且 Q 不等于 0, 则在模 MOD 下的结果为: P×Q 的逆元, 其中 Q 的逆元满足: Q×Q 的逆元 ≡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
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[ ms] | |||
| 内存最少[ KB] | |||
| 第一AC | |||
| 第一挑战 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|