P8359 [SNOI2022] Garbage Collection.

Normally, programming languages make one of the following choices when managing memory: - Let users manage memory manually (C, C++, Rust, etc.). This usually gives good performance, but also places a heavy programming burden on users. - Use a garbage collection system (Java, Go, etc.). This requires maintaining a runtime system, and it introduces many unpredictable costs in memory usage and program performance. Despite many issues, the most widely used automatic memory management approach is still the Tracing Garbage Collector. The basic idea is to maintain reference relationships between objects to form a graph. Each time collection happens, it scans the reference graph to deduce which objects can no longer be reached, and frees the memory they occupy. The biggest problem with this traditional approach is that maintaining reference chains is expensive, and as the number of maintained objects increases, the scanning cost also increases. Little L is a girl who likes thinking. She found that maintaining a Garbage Collector is very complicated, so she decided to consider a simpler model (note that it may be completely different from any real-world GC rules!). You are given an undirected graph with $n$ vertices and $m$ edges, with no multiple edges or self-loops. Vertices and edges are both numbered starting from $1$. Each vertex represents an object that occupies some amount of memory, and each edge corresponds to a reference relationship (note that the reference relationship here is **undirected**). The program starts running at time $0$ and ends at time $q + 1$. For each time $i = 1, 2, 3, \dots, q$, exactly one of the following two operations happens: - DELETE $i$: delete the edge $(x_i, y_i)$, and it is guaranteed that you will not delete an edge that has already been deleted. - GC: perform one garbage collection, i.e., kill all vertices that are not reachable from the start vertex, and free the memory they occupy. (Note that deleting vertices here does not delete the edges connected to these vertices.) You may assume that these operations are completed instantly. After all operations are done, i.e., at time $q + 1$, the program ends and deletes all remaining vertices (including vertex $1$). The memory occupied by vertex $i$ is $a_i$. You need to compute $\sum_{i = 1}^{n} a_i \cdot \mathit{alive}_i$, where $\mathit{alive}_i$ is the time that vertex $i$ stays alive. At time $0$, all vertices are alive.

The first line contains three positive integers $n, m, q$, representing the number of objects, the number of reference relationships, and the number of operations. The next $m$ lines each contain two positive integers $x_i, y_i$, describing the two endpoints of the $i$-th reference relationship. The next $q$ lines are each in one of the following two forms. The $i$-th line describes the operation at time $i$: - The string DELETE and a positive integer $x$, with the meaning described in **Description**. - The string GC, with the meaning described in **Description**. The next line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the memory size occupied by each object.

Output one line with one integer, the answer as described in **Description**.

**Sample 1 Explanation** At time $4$, vertex $5$ is deleted. At time $6$, vertices $2, 3$ are deleted. At time $9$, vertices $1, 4, 6$ are deleted. So the answer is $5 \times 4 + (2 + 3) \times 6 + (1 + 4 + 6) \times 9 = 20 + 30 + 99 = 149$. **Constraints** For all testdata, $1 \leq n, m, q \leq 4 \times 10^5$, $1 \leq a_i \leq 10^8$. The detailed constraints are shown in the table below. | Test Point ID | $n$ | $m$ | $q$ | Special Restriction | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1 \sim 2$ | $\leq 500$ | $\leq 500$ | $\leq 500$ | | | $3 \sim 5$ | $\leq 3000$ | $\leq 3000$ | $\leq 3000$ | | | $6 \sim 10$ | $\leq 5000$ | $\leq 5000$ | $\leq 5000$ | | | $11 \sim 14$ | $\leq 2 \times 10^5$ | $n-1$ | $\leq 2 \times 10^5$ | It is guaranteed that the initial graph is a tree. | | $15 \sim 16$ | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | | | $17 \sim 20$ | $\leq 4 \times 10^5$ | $\leq 4 \times 10^5$ | $\leq 4 \times 10^5$ | | Translated by ChatGPT 5