A6602. 「SNOI2022」垃圾回收

通常的情况下，编程语言在管理内存时进行如下的选择：

- 让用户进行手动内存管理（C, C++, Rust 等），这会收获很好的性能，但是给用户提供了很大的编程负担。
- 使用垃圾回收系统（Java，Go 等），这需要维护一个运行时系统，并且在内存使用和程序性能方面造成了许多不可预测的负担。

尽管存在许多的问题，目前最通用的自动化内存管理手段始终为 Tracing Garbage Collector。这种做法的最基础的思路是维护对象间的引用关系，形成一张图，每次回收时通过扫描引用关系推导出已经无法被访问到的对象，释放它们占用的内存。而这种传统的做法最大的问题在于维护引用链需要造成很大的开销，并且随着维护的对象越多，扫描的代价也会越大。

小 L 是一个喜欢思考的女孩子，她发现维护 Garbage Collector 是一件非常复杂的事情，于是她决定考虑一个更简单的模型（注意它与任何现实中的 GC 规则可能是完全不同的！）。

对于一个 $n$ 个点 $m$ 条边的无向图，没有重边自环，点和边均从 $1$ 开始标号。其中每个节点代表一个占用了一定内存的对象，每条边对应一个引用关系（注意这里的引用关系是**无向**的），程序从第 $0$ 秒开始运行，在第 $q + 1$ 秒结束运行。对于 $i = 1, 2, 3, \dots, q$ 的每个时刻 $i$ 发生以下两种操作之一：

- DELETE $i$，删除边 $(x_i,y_i)$，保证不会删除已经被删除的边。
- GC，进行一次内存回收，即杀死所有从起点出发不能访问到的点，释放它们占用的内存。（注意这里对节点的删除不会删除与这些点相连的边）

你可以认为这些操作是被瞬间执行完成的，在所有操作执行后，也就是第 $q + 1$ 秒，程序结束，删除所有剩余的节点（包括 $1$ 号点）。

第 $i$ 个点占用的内存为 $a_i$，现在请你求出 $\sum_{i = 1}^{n} a_i \cdot t_i$，这里 $t_i$ 表示第 $i$ 个点存活的时间，在第 $0$ 秒，所有节点都是存活的。

输入的第一行是三个正整数 $n, m, q$，分别表示对象的个数，引用关系的个数，操作的个数。

接下来的 $m$ 行每行 $2$ 个正整数 $x_i, y_i$ 表示第 $i$ 条引用关系的两个端点。

接下来的 $q$ 行每行为以下两种形式之一，第 $i$ 行表示在第 $i$ 秒发生的操作：

- 字符串 DELETE 和正整数 $x$，含义见「题目描述」
- 字符串 GC，含义见「题目描述」

接下来的一行有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个对象占用的内存大小。

输出一行一个整数表示程序的开销，含义见「题目描述」。

对于全部数据，$1\le n,m,q\le 4\times 10^5,1\le a_i\le 10^8$。

具体的数据规模与约定见下表。

| 测试点编号 | $n$ | $m$ | $q$ | 特殊约定 |
| :---------: | :----------------: | :-----------------: | :----------------: | :------------------: |
| $1\sim 2$ | $\le 500$ | $\le 500 $ | $\le 500$ | 无 |
| $3\sim 5$ | $\le 3000$ | $\le 3000 $ | $\le 3000$ | 无 |
| $6\sim 10$ | $\le 5000$ | $\le 5000 $ | $\le 5000$ | 无 |
| $11\sim 14$ | $\le 2\times 10^5$ | $n-1$ | $\le 2\times 10^5$ | 保证一开始图是一棵树 |
| $15\sim 16$ | $\le 2\times 10^5 $ | $\le 2\times 10^5$ | $\le 2\times 10^5 $ | 无 |
| $17\sim 20$ | $\le 4\times 10^5$ | $\le 4\times 10^5 $ | $\le 4\times 10^5$ | 无 |