| 2025 ICPC, Chula Selection Contest |
|---|
| Закончено |
The Forgotten Caverns form a network of $$$n$$$ chambers, connected by $$$m$$$ bidirectional tunnels. This network is a connected, undirected, unweighted graph with vertices numbered from $$$1$$$ to $$$n$$$.
Each chamber $$$i$$$ has a difficulty value $$$a_i$$$. Some chambers also contain ancient treasures, indicated by $$$b_i \in \{0,1\}$$$: if $$$b_i=1$$$, there is a treasure in chamber $$$i$$$; if $$$b_i=0$$$, there is none.
You are an adventurer exploring these caverns. You begin in some chamber with magical power $$$p$$$. From your current chamber $$$u$$$, you may move to any adjacent chamber $$$v$$$ through a tunnel:
You may visit the same chamber any number of times, and you may use the same tunnel any number of times.
You are asked to process $$$q$$$ queries of the following two types:
The treasure configuration is persistent and updates after each type-2 query.
The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$n-1 \le m \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of chambers, tunnels, and queries respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the difficulty of each chamber.
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$b_i \in \{0,1\}$$$) — the initial treasure configuration.
The next $$$m$$$ lines each contain two integers $$$x, y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — a tunnel between chambers $$$x$$$ and $$$y$$$.
The next $$$q$$$ lines each describe one query:
It is guaranteed that the graph is connected, with no multiple edges and no self-loops.
It is guaranteed that there will be at least one type-1 query.
For each query of type-1, output a single integer — the minimum number of coins required.
5 7 86 12 10 15 51 0 1 0 02 34 51 33 44 15 32 51 1 61 4 152 3 41 1 61 1 92 2 41 2 201 3 10
16 0 29 14 0 4
In the first example, the difficulties are $$$a = [6,12,10,15,5]$$$ and the initial treasures are at chambers $$$\{1,3\}$$$.
| Название |
|---|


