1011. 树形广播

题目描述

一座大型研究基地铺设了一套树形通信网络。网络中有 $n$ 个中继节点，编号为 $1$ 到 $n$，任意两个节点之间都存在唯一的通信路径。每个节点都带有一块状态显示屏，开机时显示值均为 $0$。

令 $\operatorname{dist}(u,v)$ 表示节点 $u$ 与节点 $v$ 之间唯一通信路径上的边数，也就是它们之间的跳数。调度中心可以从某个节点发出「分层广播」：处在不同距离的节点，会根据距离得到不同的显示值。

你需要处理 $q$ 次操作：

• $\texttt{1 v l r k}$ $w_0\ w_1\ \ldots\ w_k$ --- 从节点 $v$ 发出一次广播。对于每个满足$$l \le \operatorname{dist}(u,v) \le r$$ 的节点 $u$，令 $d=\operatorname{dist}(u,v)$，并将其显示值覆盖为$$\left(\sum_{i=0}^{k} w_i d^i\right) \bmod 998244353.$$多项式次数满足 $0 \le k \le 10$。 系数按照次数从低到高的顺序给出：$w_0$ 是常数项系数，一般地，$w_i$ 是 $d^i$ 的系数。 公式中的所有运算（包括乘方、乘法与求和）都在模 $998244353$ 意义下进行。
• $\texttt{2 x}$ --- 查看节点 $x$ 的当前显示值。

显示屏不会把新结果与旧结果相加。每次广播都会直接覆盖范围内节点原有的显示值。因此，如果多次广播都能影响同一个节点，只有时间最晚的那一次决定它当前显示的内容。

节点是否受到一次广播影响，只由它与广播中心的跳数决定。范围外的节点保持不变；若不存在跳数位于 $[l,r]$ 内的节点，则该次广播不会改变任何显示值。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10$），表示这个单一输入文件中包含的测试场景组数。

每组场景的第一行包含两个整数 $n$ 和 $q$（$1 \le n,q \le 10^5$），分别表示中继节点数和操作数。

接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a,b \le n$，$a \ne b$），表示节点 $a$ 与节点 $b$ 之间有一条双向通信线路。给出的所有线路构成一棵树。

接下来 $q$ 行，每行按照以下格式之一描述一次操作：

• $\texttt{1 v l r k}$ $w_0\ w_1\ \ldots\ w_k$（$1 \le v \le n$，$0 \le l \le r \le n-1$，$0 \le k \le 10$，$0 \le w_i < 998244353$）--- 从节点 $v$ 发出一次分层广播。 该操作中恰好给出 $k+1$ 个系数。
• $\texttt{2 x}$（$1 \le x \le n$）--- 查看节点 $x$ 的当前显示值。

保证所有测试场景的 $n$ 之和不超过 $10^6$，$q$ 之和不超过 $10^6$。

输出格式

对于每组测试场景中每次类型为 $2$ 的操作，单独输出一行一个整数，表示所查询节点显示屏上的当前数值。

答案按照输入中的操作顺序连续输出，不要在两组测试场景之间输出空行。

样例输入

2
5 9
1 2
2 3
2 4
4 5
2 3
1 2 1 2 0 7
2 2
2 5
1 5 1 3 1 2 3
2 4
2 3
2 1
2 5
6 9
1 2
1 3
3 4
3 5
5 6
1 3 0 2 2 1 2 3
2 6
1 1 1 1 0 0
2 3
2 4
1 2 2 4 10 1 0 0 0 0 0 0 0 0 0 1
2 3
2 6
2 2

样例输出

0
0
7
5
11
11
7
17
0
6
1025
1048577
0

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1011