桃树 (4s, 512M)
你有一棵 $n$ 个点的桃树,桃树的根节点为 $1$,树上每个节点都有一个桃子,树上每条边的长度都为 $1$,节点 $u$ 上的桃子的重量为 $x_u$,树上两点的距离为这两点中唯一简单路径的边长之和。
在接下来的 $Q$ 天内,每天你都将做以下 $4$ 种操作之一:
- 操作 $1$:选择一个节点 $u$,测量 $u$ 上的桃子的重量。注意,你不会将桃子摘下,测量完后 $u$ 上的桃子重量保持不变。
- 操作 $2$:选择一个节点 $u$ 和三个非负整数 $k,c,d$,对与 $u$ 距离 $\le k$ 的所有节点上的桃子施加魔法。具体而言,对于所有 $v$ 满足 $u,v$ 在树上的距离 $\le k$,将 $x_v$ 变为 $x_v\times c+d$。
- 操作 $3$:选择一个节点 $u$ 和两个非负整数 $c,d$,对 $u$ 子树内的所有节点上的桃子施加魔法。具体而言,对于所有 $v$ 满足 $v$ 在 $u$ 的子树中,将 $x_v$ 变为 $x_v\times c+d$。
- 操作 $4$:选择两个节点 $u,v$ 和两个非负整数 $c,d$,对 $u,v$ 最短路径上的所有节点上的桃子施加魔法。具体而言,对于所有 $w$ 满足 $w$ 在 $u,v$ 的最短路径上(包含 $u,v$),将 $x_v$ 变成 $x_v\times c+d$
对于每次操作 $1$,输出你测量的结果。
输入格式
第一行两个正整数 $n,Q$。
后面 $n-1$ 行每行两个正整数表示一条树边 $(u,v)$。
后面一行 $n$ 个非负整数依次表示 $x_i$。
后面 $Q$ 行每行表示一天的操作,有如下四种形式的输入,变量名的意思与题面描述相同:
1 u
2 u k c d
3 u c d
4 u v c d
输出格式
对于每个 $1$ 操作,输出一行一个非负整数表示答案。输出需要对 $998244353$ 取模。
样例 1 输入
7 12
1 2
2 3
1 4
4 5
1 6
6 7
0 0 0 0 0 0 0
2 1 2 10 1
3 1 10 2
4 2 5 10 3
3 2 10 4
2 3 2 10 5
1 1
1 2
1 3
1 4
1 5
1 6
1 7
样例 1 输出
1235
12345
1245
123
123
12
12
样例 2 $\sim$ 6
见选手目录下 $tree/ex\_tree2\sim 6.in$ 和 $tree/ex\_tree2\sim 6.out$。
数据分别满足子任务 $2\sim 6$ 的限制。
数据范围
保证所有数据满足:$2\le n,Q\le 10^5$,$0\le c,d<998244353$,$0\le k\le 10$。
Subtask | $n,Q$ | $k$ | 操作种类 | 分值 |
---|---|---|---|---|
$1$ | $\le 1000$ | $\le 10$ | $1,2,3,4$ | $10$ |
$2$ | $\le 10^5$ | $\le 10 $ | $1,2$ | $15$ |
$3$ | $\le 10^5$ | $=1$ | $1,2,3$ | $15$ |
$4$ | $\le 10^5$ | $\le 10 $ | $1,3,4$ | $15$ |
$5$ | $\le 10^5$ | $=1$ | $1,2,3,4$ | $18$ |
$6$ | $\le 10^5 $ | $\le 10$ | $1,2,3,4$ | $27$ |