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


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: