题目背景

译自 Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{1.5s,0.5G}$。

题目描述

给定 $n$ 个点 $m$ 条边的无向图（不一定连通，无自环，可能有重边）。

点 $i$ 的点权为 $a_i$。此外，图中有若干个点是关键点。

定义关键点 $u$ 的影响力为：不经过其他关键点（也不从其他关键点出发），且能到达点 $u$ 的点的点权和。

有 $q$ 次操作：

• $\texttt{1}$ $u$ $x$：令 $a_u\gets x$；
• $\texttt{2}$ $v$：查询关键点 $v$ 的影响力。

依次处理之，并对每个操作 $2$ 输出答案。

输入格式

第一行，两个正整数 $n,m$;

第二行，$n$ 个非零即一的整数 $x_1,x_2,\cdots,x_n$。点 $i$ 是关键点当且仅当 $x_i=1$。

第三行，$n$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示图中的一条边。

接下来一行，一个正整数 $q$。

接下来 $q$ 行，每行若干个整数描述一个操作。

输出格式

对于每个操作 $2$，输出一行一个整数表示答案。

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

22
8

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

6
11
19
13
14

提示

对于 $100\%$ 的数据，保证：

• $1\le n,m,q\le 2\times 10^5$；
• $0\le a_i,x\le 10^9$；
• $1\le u,v\le n$；
• 图中无自环；
• 操作 $2$ 中给定的点 $v$ 是关键点。

特殊性质 A：没有操作 $1$。