← 返回比赛
已结束 GESP挑战赛#10
← 上一题 下一题 →

A4550 | Ptorrweee

来源官方 / 2024
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

~~由于这是最后一题，所有没有故事背景。~~

这是 Elbisivid 给 Ytiroirp 出的一道题，需要你来帮帮 Ytiroirp。

---

给定一棵有根树，树根为 $1$，初始点权均为 $0$。

有 $q$ 次操作，形如

- 1 u x，表示将 $u$ 的子树内的节点 $v$ 的点权增加上 $a^{x+dis(u,v)}$，其中 $dis(u,v)$ 表示 $u,v$ 之间的距离。

- 2 u，求出节点 $u$ 的当前点权。

$a$ 是事先给定的，在询问中不会更改。答案对 $998244353$ 取模。

输入格式

第一行两个正整数，分别表示 $n,q,a$；

接下来的 $n-1$ 行，每行两个整数，$u,v$ 表示树的一条边。

接下来的 $q$ 行，每行表示一个操作，可能是 1 u x 或者 2 u 的格式，含义参考题面。

输出格式

对于每一个 2 操作，输出答案。

输入输出样例

输入 #1
5 8 7
1 2
1 3
3 4
3 5
1 1 0
2 1
2 2
2 4
1 3 1
2 3
2 4
2 1
输出 #1
1
7
49
14
98
1
C++ 编辑器
输入
输出