黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有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)时才会被视为正确。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=100010;

int n,m,cnt,rt;

int dep[maxn],fa[20][maxn],siz[maxn],p[maxn],q[maxn],to[maxn<<1],next[maxn<<1],head[maxn],Log[maxn];

char str[20];

struct LCT

{

	int ch[2],rev,fa;

}s[maxn];

struct BIT

{

	ll s[maxn];

	inline void updata(int x,ll val)

	{

		for(int i=x;i<=n;i+=i&-i)	s[i]+=val;

	}

	inline ll query(int x)

	{

		ll ret=0;

		for(int i=x;i;i-=i&-i)	ret+=s[i];

		return ret;

	}

}s1,s2;

inline bool isr(int x)	{return s[s[x].fa].ch[0]!=x&&s[s[x].fa].ch[1]!=x;}

inline void pushdown(int x)

{

	if(s[x].rev)

	{

		swap(s[x].ch[0],s[x].ch[1]);

		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;

		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;

		s[x].rev=0;

	}

}

void updata(int x)

{

	if(!isr(x))	updata(s[x].fa);

	pushdown(x);

}

inline void rotate(int x)

{

	int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);

	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;

	s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];

	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;

	s[x].ch[d^1]=y;

}

inline void splay(int x)

{

	updata(x);

	while(!isr(x))

	{

		int y=s[x].fa,z=s[y].fa;

		if(!isr(y))

		{

			if((x==s[y].ch[0])^(y==s[z].ch[0]))	rotate(x);

			else	rotate(y);

		}

		rotate(x);

	}

}

inline void sumup(int x,ll val)

{

	s1.updata(x,val*x),s2.updata(x,val);

}

inline ll getsum(int x)

{

	return (s2.query(n)-s2.query(x))*x+s1.query(x);

}

inline int find(int x,int y)

{

	for(int i=Log[y];i>=0;i--)	if((1<<i)<=y)	x=fa[i][x],y-=(1<<i);

	return x;

}

inline void modify(int &x,ll val)

{

	if(!x)	return ;

	pushdown(x);

	while(s[x].ch[0])	x=s[x].ch[0],pushdown(x);

	splay(x);

	if(x==rt)	sumup(n,val);

	else	if(p[rt]<p[x]||p[rt]>q[x])	sumup(p[x]-1,-val),sumup(q[x],val);

	else

	{

		int y=find(rt,dep[rt]-dep[x]-1);

		sumup(p[y]-1,val),sumup(q[y],-val),sumup(n,val);

	}

}

inline double getans(int x)

{

	if(x==rt)	return (double)getsum(n)/n;

	else	if(p[rt]<p[x]||p[rt]>q[x])	return (double)(getsum(q[x])-getsum(p[x]-1))/(q[x]-p[x]+1);

	else

	{

		int y=find(rt,dep[rt]-dep[x]-1);

		return (double)(getsum(p[y]-1)+getsum(n)-getsum(q[y]))/(p[y]-1+n-q[y]);

	}

}

inline void access(int x)

{

	for(int y=0,t;x;)

		splay(x),t=s[x].ch[1],modify(y,-1),s[x].ch[1]=y,modify(t,1),y=x,x=s[x].fa;

}

inline void maker(int x)

{

	access(x),splay(x),s[x].rev^=1,rt=x;

}

inline void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

void dfs(int x)

{

	siz[x]=1,p[x]=++q[0];

	for(int i=head[x];i!=-1;i=next[i])

		if(to[i]!=fa[0][x])	fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]),siz[x]+=siz[to[i]];

	q[x]=q[0];

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd(),rt=1;

	int i,j,a,b;

	memset(head,-1,sizeof(head));

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	dep[1]=1,dfs(1);

	for(i=2;i<=n;i++)	Log[i]=Log[i>>1]+1;

	for(j=1;(1<<j)<=n;j++)	for(i=1;i<=n;i++)	fa[j][i]=fa[j-1][fa[j-1][i]];

	for(i=1;i<=n;i++)	s1.updata(p[i],dep[i]),s[i].fa=fa[0][i];

	//for(j=1;j<=n;j++)	printf("%lld%c",getsum(p[j])-getsum(p[j]-1),j==n?'\n':' ');

	for(i=1;i<=m;i++)

	{

		scanf("%s",str),a=rd();

		if(str[2]=='L')	access(a),splay(a);

		if(str[2]=='C')	maker(a);

		if(str[2]=='Q')	printf("%.10lf\n",getans(a));

		//for(j=1;j<=n;j++)	printf("%lld%c",getsum(p[j])-getsum(p[j]-1),j==n?'\n':' ');

	}

	return 0;

}//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