重组病毒

时间限制:20s      空间限制:512MB

题目描述

黑客们通过对已有的病毒反编译,将许多不同的病毒重组,并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播,某安全机构策划了一次实验,来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有n台计算机,编号为1~n。一些计算机之间通过网线直接相连,形成树形的结构。局域网中有一台特殊的计算机,称之为核心计算机。根据一些初步的研究,研究员们拟定了一个一共m步的实验。实验开始之前,核心计算机的编号为1,每台计算机中都有病毒的一个变种,而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作:
1、 RELEASE x
在编号为x的计算机中植入病毒的一个新变种。这个变种在植入之前不存在于局域网中。
2、 RECENTER x
将核心计算机改为编号为x的计算机。但是这个操作会导致原来核心计算机中的病毒产生新变种,并感染过来。换言之,假设操作前的核心计算机编号为y,相当于在操作后附加了一次RELEASE y的操作。
根据研究的结论,在植入一个新变种时,病毒会在局域网中搜索核心计算机的位置,并沿着网络中最短的路径感染过去。
而第一轮实验揭露了一个惊人的真相:病毒的不同变种是互斥的。新变种在感染一台已经被旧变种感染的电脑时,会把旧变种完全销毁之后再感染。但研究员发现了实现过程中的漏洞。如果新变种在感染过程中尚未销毁过这类旧变种,需要先花费1单位时间分析旧变种,才能销毁。如果之前销毁过这类旧变种,就可以认为销毁不花费时间。病毒在两台计算机之间的传播亦可认为不花费时间。
研究员对整个感染过程的耗时特别感兴趣,因为这是消灭病毒的最好时机。于是在m步实验之中,研究员有时还会做出如下的询问:
3、 REQUEST x
询问如果在编号为x的计算机的关键集合中的计算机中植入一个新变种,平均感染时间为多长。编号为y的计算机在编号为x的计算机的关键集合中,当且仅当从y沿网络中的最短路径感染到核心计算机必须经过x。由于有RECENTER操作的存在,这个集合并不一定是始终不变的。
至此,安全机构认为已经不需要实际的实验了,于是他们拜托你编写一个程序,模拟实验的结果,并回答所有的询问。


输入格式

输入的第一行包含两个整数n和m,分别代表局域网中计算机的数量,以及操作和询问的总数。
接下来n-1行,每行包含两个整数x和y,表示局域网中编号为x和y的计算机之间有网线直接相连。
接下来m行,每行包含一个操作或者询问,格式如问题描述中所述。


输出格式

对于每个询问,输出一个实数,代表平均感染时间。输出与答案的绝对误差不超过 10^(-6)时才会被视为正确。


样例输入

8 6
1 2
1 3
2 8
3 4
3 5
3 6
4 7
REQUEST 7
RELEASE 3
REQUEST 3
RECENTER 5
RELEASE 2
REQUEST 1

样例输出

4.0000000000
2.0000000000
1.3333333333

提示

N < = 1 00 000 M < = 1 00 000


题目来源

没有写明来源

Menuappsclose