[AdditionalFile5279.zip](file://AdditionalFile5279.zip?type=additional_file)

#5279. 「UOI 2019 Stage 4 Day2」皮罗格兰迪亚

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 14 及以上）

请在提交源代码前添加 #include "grader.h"。

题目描述

题目译自 Ukrainian Olympiads in Informatics 2019 Stage 4 Day2 T4. Пироголяндiя

众所周知，皮罗格兰迪亚是一个居民非常喜欢派的国家。因此，国内建有 $n$ 家面包店，每家面包店有一个唯一的整数编号，从 $1$ 到 $n$。每家面包店都有一个仓库，存储一定数量的派，其中编号为 $i$ 的面包店仓库中有 $a_i$ 个派。

此外，一些面包店之间铺设有道路，可以通过这些道路将派从一个面包店运送到另一个面包店。总共铺设了 $n-1$ 条道路，每条道路有一个唯一的整数编号，从 $1$ 到 $n-1$。第 $i$ 条道路连接面包店 $u_i$ 和 $v_i$，即可以在面包店 $u_i$ 和 $v_i$ 的仓库之间运输任意数量的派。

面包店 $u$ 和 $v$ 之间的路径定义为一系列唯一的面包店编号序列 $p_1, p_2, \ldots , p_k$，使得每对相邻的面包店 $p_i$ 和 $p_{i+1}$（对于 $i$ 从 $1$ 到 $k-1$）之间存在一条道路，且 $p_1 = u$ 以及 $p_k = v$。已知每对面包店之间存在且仅存在一条不重复访问任何面包店的路径。

在皮罗格兰迪亚，有时会发生地震，导致一些道路可能被封锁，无法运输派。此外，道路维修服务有时会修复某些道路，使其重新可用于运输。因此，每条道路有两种状态：未封锁或封锁。

面包店 $u$ 的连通分量定义为所有可以通过未封锁道路从编号为 $u$ 的面包店到达的面包店集合。面包店 $u$ 本身也包含在其连通分量中。

皮罗格兰迪亚最著名的居民之一是科扎克·武斯，他因在年度派爱好者节上吃掉最多派而广受欢迎。

在皮罗格兰迪亚，有时会发生与面包店、道路以及我们的朋友科扎克·武斯相关的各种事件。你需要处理 $m$ 个事件，这些事件以不同类型的查询形式给出，并能够回答其中一些查询。

总共有 $7$ 种类型的查询：

1. 改变编号为 $p$ 的道路的状态为相反状态。即如果查询前道路 $p$ 是封锁的，则将其变为未封锁；如果之前是未封锁的，则将其变为封锁。
2. 向编号为 $p$ 的面包店所在连通分量中的每家面包店的仓库增加 $w$ 个派。即如果面包店 $u$ 属于面包店 $p$ 的连通分量，则将 $a_u$ 增加 $w$。
3. 将编号为 $p$ 的面包店所在连通分量中所有面包店的派全部运输到编号为 $p$ 的面包店仓库中。即在查询后，编号为 $p$ 的面包店仓库中将存储其连通分量中所有面包店的派，而该连通分量中其他面包店的仓库将变为空。
4. 科扎克·武斯想知道编号为 $p$ 的面包店仓库中存储的派数量，即 $a_p$ 的值。
5. 科扎克·武斯想知道编号为 $p$ 的面包店所在连通分量中所有面包店仓库存储的派总数。
6. 科扎克·武斯吃掉编号为 $p$ 的面包店所在连通分量中每家面包店仓库中的所有派。即在查询后，对于属于面包店 $p$ 连通分量的每家面包店 $u$，$a_u$ 的值应为 $0$。
7. 科扎克·武斯想知道需要修复的最小道路数量，以便他能吃掉皮罗格兰迪亚所有面包店仓库中的派，假设他可以从任意面包店开始，并且只能通过未封锁的道路移动。

请注意，类型为 $4$、$5$ 和 $7$ 的查询不会对面包店和道路产生任何影响，仅需提供答案。

交互方式

你需要实现以下八个函数：

void init(integer n, array of integers u, array of integers v, array of integers b, array of integers a, integer g)

• $n$ —— 皮罗格兰迪亚的面包店数量；
• $u_i$ 和 $v_i$ $(|u|=|v|=n-1)$—— 连接第 $i$ 条道路的面包店编号；
• $b_i$ $(|b|=n-1)$—— 如果第 $i$ 条道路是封锁的，则为 $1$，否则为 $0$；
• $a_i$ $(|a|=n)$—— 第 $i$ 家面包店的初始派数量；
• $g$ —— 子任务编号；
• 该函数首次调用，仅调用一次，用于告知你皮罗格兰迪亚的面包店数量、道路连接的面包店对、每条道路的状态、每家面包店仓库的初始派数量以及子任务编号。只有在调用该函数后，才会调用其他七个函数。

void query_1(integer p)

• $p$ —— 需要改变状态的道路编号；
• 该函数在需要执行第一类型查询时调用。

void query_2(integer p, integer w)

• $p$ —— 面包店编号；
• $w$ —— 向编号为 $p$ 的面包店所在连通分量中每家面包店增加的派数量；
• 该函数在需要执行第二类型查询时调用。

void query_3(integer p)

• $p$ —— 面包店编号；
• 该函数在需要执行第三类型查询时调用。

integer query_4(integer p)

• $p$ —— 面包店编号；
• 该函数在需要执行第四类型查询时调用；
• 函数应返回一个整数，表示查询的答案。

integer query_5(integer p)

• $p$ —— 面包店编号；
• 该函数在需要执行第五类型查询时调用；
• 函数应返回一个整数，表示查询的答案。

void query_6(integer p)

• $p$ —— 面包店编号；
• 该函数在需要执行第六类型查询时调用。

integer query_7()

• 该函数在需要执行第七类型查询时调用；
• 函数应返回一个整数，表示查询的答案。

输入格式

第一行包含三个整数 $n, m, g$ $(1 \leq n, m \leq 250000, 0 \leq g \leq 11)$，分别表示皮罗格兰迪亚的面包店数量、事件数量和子任务编号。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ $(1 \leq u_i, v_i \leq n)$，表示连接第 $i$ 条道路的面包店对。保证每对面包店之间存在且仅存在一条路径。

下一行包含一个长度为 $n-1$ 的字符串，由字符 $0$ 或 $1$ 组成。第 $i$ 个字符为 $1$ 表示第 $i$ 条道路是封锁的，为 $0$ 表示未封锁。

再下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^{5})$，表示每家面包店仓库的初始派数量。

接下来的 $m$ 行，每行描述一个查询。行首数字表示查询类型。如果是类型 $2$ 查询，行内还包含两个参数 $p$ $(1 \leq p \leq n)$ 和 $w$ $(0 \leq w \leq 10^{5})$。如果是类型 $1$ 查询，行内包含一个额外参数 $p$ $(1 \leq p \leq n-1)$。如果是类型 $3$ 到 $6$ 查询，行内包含一个额外参数 $p$ $(1 \leq p \leq n)$。如果是类型 $7$ 查询，行内不包含额外参数。

输出格式

对于类型 $4$、$5$ 和 $7$ 的查询，在单独的一行上输出答案。

样例

输入

5 11 0
1 2
1 3
3 4
3 5
0100
1 0 6 1 3
5 3
3 4
2 5 4
4 3
7
6 4
1 2
5 4
2 2 1
1 3
5 2

输出

10
4
1
1
5

在图示中，面包店以圆形表示，圆内有两个整数——面包店编号和仓库中派的数量。未封锁的道路以实线表示，封锁的道路以虚线表示。

在图 $0$ 中，展示了皮罗格兰迪亚在所有变化前的状态。编号为 $2$ 的道路（连接面包店 $1$ 和 $3$）是封锁的。面包店 $1$ 的连通分量（与面包店 $2$ 的连通分量相同）包含面包店 $1$ 和 $2$。面包店 $3$、$4$ 和 $5$ 的连通分量包含面包店 $3$、$4$ 和 $5$，因此面包店 $3$ 所在连通分量的派总数为 $6 + 1 + 3 = 10$。

在第二个查询后（图 $1$），面包店 $3$ 和 $5$ 将它们的派运输到面包店 $4$ 的仓库中。

在第三个查询后（图 $2$），向面包店 $3$、$4$ 和 $5$ 的仓库各增加了 $4$ 个派，因此面包店 $3$ 仓库中的派数量现在为 $4$。除了面包店 $2$ 外，每家面包店的仓库中至少有 $1$ 个派。如果科扎克·武斯从面包店 $1$ 或 $2$ 开始他的路径，他需要修复编号为 $2$ 的道路才能到达面包店 $3$。如果他从面包店 $3$、$4$ 或 $5$ 开始，则仍需修复编号为 $2$ 的道路才能到达面包店 $1$。因此，第五个查询的答案为 $1$。

在第六个查询后（图 $3$），科扎克·武斯吃掉了面包店 $3,4,5$ 仓库中的所有派。

在第七个查询后（图 $4$），道路维修服务修复了编号为 $2$ 的道路，因此它现在变为未封锁状态。现在面包店 $1$ 的连通分量（与其他所有面包店相同）包含皮罗格兰迪亚的所有面包店。因此，第八个查询的答案为 $0 + 1 + 0 + 0 + 0 = 1$。

在第九个查询后（图 $5$），每家面包店的仓库中各增加了 $1$ 个派。

在第十个查询后（图 $6$），由于地震，编号为 $3$ 的道路被破坏，因此它变为封锁状态。现在面包店 $1$ 的连通分量包含除面包店 $4$ 外的所有面包店，而面包店 $4$ 的连通分量仅包含它自身。因此，最后一个查询的答案为 $2 + 1 + 1 + 1 = 5$。

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$2$	$n \leq 3000$；$m \leq 3000$；无类型 $1$ 和 $7$ 查询；所有道路初始为封锁
$2$	$3$	$n \leq 3000$；$m \leq 3000$；无类型 $1$ 和 $7$ 查询；所有道路初始为未封锁
$3$	$5$	$n \leq 3000$；$m \leq 3000$；无类型 $1$ 和 $7$ 查询
$4$	$6$	$n \leq 3000$；$m \leq 3000$；无类型 $7$ 查询
$5$	$8$	$n \leq 3000$；$m \leq 3000$
$6$	$10$	无类型 $1$ 和 $7$ 查询
$7$	$16$	无类型 $7$ 查询；类型 $1$ 查询中道路状态仅从封锁变为未封锁
$8$	$15$	无类型 $1$ 查询
$9$	$9$	无类型 $7$ 查询
$10$	$17$	每家面包店最多与两家其他面包店连接道路
$11$	$9$	无附加限制