{"problem":{"name":"[SNOI2022] 垃圾回收","description":{"content":"通常的情况下，编程语言在管理内存时进行如下的选择： - 让用户进行手动内存管理（C、C++、Rust 等），这会收获很好的性能，但是给用户提供了很大的编程负担。 - 使用垃圾回收系统（Java、Go 等），这需要维护一个运行时系统，并且在内存使用和程序性能方面造成了许多不可预测的负担。 尽管存在许多的问题，目前最通用的自动化内存管理手段始终为 Tracing Garbage Collector","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8359"},"statements":[{"statement_type":"Markdown","content":"通常的情况下，编程语言在管理内存时进行如下的选择：\n\n- 让用户进行手动内存管理（C、C++、Rust 等），这会收获很好的性能，但是给用户提供了很大的编程负担。\n- 使用垃圾回收系统（Java、Go 等），这需要维护一个运行时系统，并且在内存使用和程序性能方面造成了许多不可预测的负担。\n\n尽管存在许多的问题，目前最通用的自动化内存管理手段始终为 Tracing Garbage Collector。这种做法的最基础的思路是维护对象间的引用关系，形成一张图，每次回收时通过扫描引用关系推导出已经无法被访问到的对象，释放它们占用的内存。而这种传统的做法最大的问题在于维护引用链需要造成很大的开销，并且随着维护的对象越多，扫描的代价也会越大。\n\n小 L 是一个喜欢思考的女孩子，她发现维护 Garbage Collector 是一件非常复杂的事情，于是她决定考虑一个更简单的模型（注意它与任何现实中的 GC 规则可能是完全不同的！）。\n\n对于一个 $n$ 个点 $m$ 条边的无向图，没有重边自环，点和边均从 $1$ 开始标号。其中每个节点代表一个占用了一定内存的对象，每条边对应一个引用关系（注意这里的引用关系是**无向**的），程序从第 $0$ 秒开始运行，在第 $q + 1$ 秒结束运行。对于 $i = 1, 2, 3, \\dots, q$ 的每个时刻 $i$ 发生以下两种操作之一：\n\n- DELETE $i$，删除边 $(x_i,y_i)$，保证不会删除已经被删除的边。\n- GC， 进行一次内存回收，即杀死所有从起点出发不能访问到的点，释放它们占用的内存。（注意这里对节点的删除不会删除与这些点相连的边）\n\n你可以认为这些操作是被瞬间执行完成的，在所有操作执行后，也就是第 $q + 1$ 秒，程序结束，删除所有剩余的节点（包括 $1$ 号点）。\n\n第 $i$ 个点占用的内存为 $a_i$，现在请你求出 $\\sum_{i = 1}^{n} a_i \\cdot \\mathit{alive}_i$，这里 $\\mathit{alive}_i$ 表示第 $i$ 个点存活的时间，在第 $0$ 秒，所有节点都是存活的。\n\n## Input\n\n输入的第一行是三个正整数 $n, m, q$，分别表示对象的个数，引用关系的个数，操作的个数。\n\n接下来的 $m$ 行每行两个正整数 $x_i, y_i$ 表示第 $i$ 条引用关系的两个端点。\n\n接下来的 $q$ 行每行为以下两种形式之一，第 $i$ 行表示在第 $i$ 秒发生的操作：\n\n- 字符串 DELETE 和正整数 $x$，含义见【题目描述】。\n- 字符串 GC，含义见【题目描述】。\n\n接下来的一行有 $n$ 个正整数 $a_1,a_2,\\dots,a_n$，表示每个对象占用的内存大小。 \n\n## Output\n\n输出一行一个整数表示答案，含义见【题目描述】。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n在第 $4$ 秒时，节点 $5$ 被删除。\n\n在第 $6$ 秒时，节点 $2, 3$ 被删除。\n\n在第 $9$ 秒时，节点 $1, 4, 6$ 被删除。\n\n答案即 $5 \\times 4 + (2 + 3) \\times 6 + (1 + 4 + 6) \\times 9 = 20 + 30 + 99 = 149$。\n\n**【数据规模与约定】**\n\n对于全部数据，$1 \\leq n, m, q \\leq 4 \\times 10^5$，$1 \\leq a_i \\leq 10^8$。\n\n具体的数据规模与约定见下表。\n\n| 测试点编号 | $n$ | $m$ | $q$ | 特殊限制 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1 \\sim 2$ | $\\leq 500$ | $\\leq 500$ | $\\leq 500$ |   |\n| $3 \\sim 5$ | $\\leq 3000$ | $\\leq 3000$ | $\\leq 3000$ |  |\n| $6 \\sim 10$ | $\\leq 5000$ | $\\leq 5000$ | $\\leq 5000$ |  |\n| $11 \\sim 14$ | $\\leq 2 \\times 10^5$ | $n-1$ | $\\leq 2 \\times 10^5$ | 保证一开始图是一棵树 |\n| $15 \\sim 16$ | $\\leq 2 \\times 10^5$ | $\\leq 2 \\times 10^5$ | $\\leq 2 \\times 10^5$ |  |\n| $17 \\sim 20$ | $\\leq 4 \\times 10^5$ | $\\leq 4 \\times 10^5$ | $\\leq 4 \\times 10^5$ |  |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8359","tags":["并查集","各省省选","2022","O2优化","陕西"],"sample_group":[["6 6 8\n1 2\n2 3\n2 4\n1 4\n2 5\n1 6\nGC\nDELETE 5\nDELETE 3\nGC\nDELETE 1\nGC\nDELETE 2\nGC\n1 2 3 4 5 6\n","149\n"],["样例 2 见附件 garbage2.in\n本组数据满足测试点 6 的限制。","样例 2 见附件 garbage2.ans"],["样例 3 见附件 garbage3.in\n本组数据满足测试点 11 的限制。","样例 3 见附件 garbage3.ans"]],"created_at":"2026-03-03 11:09:25"}}