#P17135. 树形广播

树形广播

1011. 树形广播

题目描述

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

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

你需要处理 qq 次操作:

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

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

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

输入格式

第一行包含一个整数 TT(1≤T≤101 \le T \le 10),表示这个单一输入文件中包含的测试场景组数。

每组场景的第一行包含两个整数 nn 和 qq(1≤n,q≤1051 \le n,q \le 10^5),分别表示中继节点数和操作数。

接下来 n−1n-1 行,每行包含两个整数 aa 和 bb(1≤a,b≤n1 \le a,b \le n,a≠ba \ne b),表示节点 aa 与节点 bb 之间有一条双向通信线路。给出的所有线路构成一棵树。

接下来 qq 行,每行按照以下格式之一描述一次操作:

  • 1 v l r k\texttt{1 v l r k} w0 w1 … wkw_0\ w_1\ \ldots\ w_k(1≤v≤n1 \le v \le n,0≤l≤r≤n−10 \le l \le r \le n-1,0≤k≤100 \le k \le 10,0≤wi<9982443530 \le w_i < 998244353)--- 从节点 vv 发出一次分层广播。 该操作中恰好给出 k+1k+1 个系数。
  • 2 x\texttt{2 x}(1≤x≤n1 \le x \le n)--- 查看节点 xx 的当前显示值。

保证所有测试场景的 nn 之和不超过 10610^6,qq 之和不超过 10610^6。

输出格式

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

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

样例输入

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