Logo Universal Online Judge

UOJ

时间限制:4 s 空间限制:512 MB

#2411. tree

统计

桃树 (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$