558 「Antileaf's Round」我们的 CPU 遭到攻击

内存限制:512 MB 时间限制:1000 ms

题目描述

攻击

给你一个有 $n$ 个点的森林,点有黑白两种颜色,初始时所有点都是白色,森林的每条边有边权,初始时这个森林有 $m$ 条边。
对这个森林进行 $k$ 次操作,操作有三种:

  • L u v w:添加一条连接 $u$ 和 $v$,长度为 $w$ 的边。
  • C u v:删除连接 $u$ 和 $v$ 的边(保证存在)。
  • F u:反转点 $u$ 的颜色(黑变白,白变黑)。
  • Q u:询问所有与 $u$ 相连的黑点到 $u$ 的距离之和。(相连指的是在同一连通块中)

输入格式

第一行三个非负整数,分别表示 $n$,$m$,$k$。
以下 $m$ 行,每行三个整数 $u$,$v$,$w$,表示初始时有一条边连接 $u$ 和 $v$,长度为 $w$。
以下 $k$ 行,每行描述一个操作,格式如上所述。

输出格式

对于每个 $ Q $ 操作,单独一行输出一个整数表示答案。

样例

我已经想到了一个绝妙的解释,可是地方太小,写不下了。

数据范围与提示

$0\le m< n\le 10^5$,$k\le 3\times 10^5$,$|w|\le 10^7$,保证任何时刻这个图均为森林(即不会出现环)。

样例

样例输入 1

5 2 7 1 2 5 3 5 -13 Q 2 F 5 L 3 4 -2 Q 4 L 2 4 7 C 1 2 Q 2

样例输出 1

0 -15 -8