6888: BZOJ2888：资源运输
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
小Y盯上了最近发行的即时战略游戏——ResourceTransport。但在前往通关之路的道路上，一个小游戏挡住了小Y的步伐。“国家的本质是生产与收集资源”是整款游戏的核心理念，这个小游戏也不例外。简单的说，用户需要管理一个国家，使其繁荣富强。
一个国家含有N个城市，游戏开始时城市间没有任何道路。城市可以通过高速公路连接。为了减少建设费用，每对城市间最多存在一条路径。
小Y拥有极强的游戏天赋，很快就把所有城市的生产能力提到了满级，把高速公路的建设费用修改成了0。
悲剧的是，对于每个连通的城市群，都要把该城市群中的某个城市设立成资源集合处，小Y把这件事忘了；更悲剧的是，建造高速公路这件事，小Y也忘了。
可小Y是个完美主义者，他请来了你帮他设立资源集合处，自己负责建造高速公路。假设连通城市群中的某个城市i到该城市群的资源集合处最少需要经过Di条高速公路，那么总运输费用为Sigma(Di)。你需要在每个连通城市群中设立一个资源集合处，使得总费用最小。小Y有时会向你询问此时最小的总费用。
问题很简单，麻烦的是小Y会在你好不容易算出最小总费用时建造一条新的高速公路。由于每个连通的城市群只能有一个资源集合处，所以最小总费用又得重新计算，这可真是个苦差事……
输入格式
第一行两个整数N，M分别表示国家中的城市数与小Y的操作数。 接下来M行，每行可能为： 1.A x y：表示在城市x和城市y间建造一条高速公路，保证此操作出现N-1次； 2.Q：表示小Y询问此时的最小总费用。
输出格式
对于每个Q操作，单独输出一行一个整数Ans，表示所求的答案。
样例输入
8 10 Q A 1 2 A 4 5 A 6 7 A 3 4 Q A 2 5 A 6 8 A 4 6 Q
样例输出
0
4
12
【样例解释】
1.开始所有城市互不联通，每个城市都是资源集合处，费用为0；
2.后来分别把城市1、城市4、城市7、城市8设立为资源集合处，费用为4；
3.最后把城市4设立为资源集合处，费用为12。提示
N<=40000,M<=80000
题目来源
没有写明来源