Description：

给一棵树，每个点一开始颜色互不相同，支持三个操作

1.将一个点到根的路径染成一种新的颜色

2.将一个新的点设为根，并将原来的根到这个点的路径染成一种新的颜色

3.查询一个子树（对于当前根）到根的路径期望颜色数

$1\leqslant n\leqslant 10^5$

Solution：

和染色那题基本是一样的，不难看出第一个操作就是 $access$ ，第二个操作就是 $makeroot$ ，第三个操作就是查询整个子树中所有点到根的轻边个数，那么就像那题一样用线段树维护 $dfs$ 序，然后在 $access$ 的时候加加减减就行了，但是这题还有换根操作，那就像遥远的国度那题一样特判一下就行了。

注意子树加的时候要找到真正的子树根。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef long long ll;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

#define I inline

namespace ST

{

	struct node

	{

		int lc,rc;

		ll sum,tag;

		node(){sum = 0;}

	}t[MAXN << 1];

	int ptr = 0;

	I int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	I void pushdown(int rt,int l,int r)

	{

		if(t[rt].tag != 0)

		{

			register int ll = l,lr = mid,rl = mid + 1,rr = r;

			t[t[rt].lc].tag += t[rt].tag;t[t[rt].lc].sum += (lr - ll + 1) * t[rt].tag;

			t[t[rt].rc].tag += t[rt].tag;t[t[rt].rc].sum += (rr - rl + 1) * t[rt].tag;

			t[rt].tag = 0;

		}

		return;

	}

	void add(int rt,int L,int R,int k,int l,int r)

	{

		if(L > R)return;

		if(L <= l && r <= R)

		{

			t[rt].sum += (r - l + 1) * k;

			t[rt].tag += k;

			return;

		}

		pushdown(rt,l,r);

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

		t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

		return;

	}

	ll query(int rt,int L,int R,int l,int r)

	{

		if(L > R)return 0;

		if(L <= l && r <= R)return t[rt].sum;

		pushdown(rt,l,r);

		register ll res = 0;

		if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

		if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

}

namespace DFN

{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	I void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

	int f[MAXN][18],dep[MAXN],siz[MAXN],rnk[MAXN],tot = 0;

	void dfs(int k,int depth)

	{

		dep[k] = depth;

		siz[k] = 1;

		rnk[k] = ++tot;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to != f[k][0])

			{

				f[e[i].to][0] = k;

				dfs(e[i].to,depth + 1);

				siz[k] += siz[e[i].to];

			}

		}

		return;

	}

	I void build()

	{

		dfs(1,1);

		for(int k = 1;k <= 17;++k)

			for(int i = 1;i <= n;++i)

				f[i][k] = f[f[i][k - 1]][k - 1];

		return;

	}

	I int LCA(int a,int b)

	{

		if(dep[a] < dep[b])swap(a,b);

		for(register int i = 17;i >= 0;--i)

			if(dep[f[a][i]] >= dep[b])a = f[a][i];

		if(a == b)return a;

		for(register int i = 17;i >= 0;--i)

			if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];

		return f[a][0];

	}

	I int skip_to_son(int k,int fa)

	{

		for(register int i = 17;i >= 0;--i)

			if(dep[f[k][i]] > dep[fa])k = f[k][i];

		return k;

	}

	int root;

	I void change(int rt,int k)

	{

		if(rt == 0)return;

		if(rt == root){ST::add(ST::root,1,n,k,1,n);return;}

		if(LCA(rt,root) != rt){ST::add(ST::root,rnk[rt],rnk[rt] + siz[rt] - 1,k,1,n);return;}

		register int v = skip_to_son(root,rt);

		ST::add(ST::root,1,rnk[v] - 1,k,1,n);

		ST::add(ST::root,rnk[v] + siz[v],n,k,1,n);

		return;

	}

	I ll query(int rt)

	{

		if(rt == root)return ST::t[ST::root].sum;

		if(LCA(rt,root) != rt)return ST::query(ST::root,rnk[rt],rnk[rt] + siz[rt] - 1,1,n);

		register int v = skip_to_son(root,rt);

		register ll res = 0;

		res += ST::query(ST::root,1,rnk[v] - 1,1,n);

		res += ST::query(ST::root,rnk[v] + siz[v],n,1,n);

		return res;

	}

	I int calcsiz(int rt)

	{

		if(rt == root)return n;

		if(LCA(rt,root) != rt)return siz[rt];

		register int v = skip_to_son(root,rt);

		register int res = 0;

		res += rnk[v] - 1;

		res += n - (rnk[v] + siz[v]) + 1;

		return res;

	}

}

namespace LCT

{

	struct node

	{

		int c[2],fa;

		int L,R;

		bool rev;

	}t[MAXN];

	I bool isroot(int rt){return (t[t[rt].fa].c[0] != rt && t[t[rt].fa].c[1] != rt);}

	I int id(int rt){return (t[t[rt].fa].c[0] == rt ? 0 : 1);}

	I void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	I void pushdown(int rt)

	{

		if(rt == 0)return;

		if(t[rt].rev)

		{

			t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

			swap(t[rt].c[0],t[rt].c[1]);swap(t[rt].L,t[rt].R);

			t[rt].rev = false;

		}

		return;

	}

	I void maintain(int rt)

	{

		pushdown(t[rt].c[0]);pushdown(t[rt].c[1]);

		if(t[rt].c[0])t[rt].L = t[t[rt].c[0]].L;else t[rt].L = rt;

		if(t[rt].c[1])t[rt].R = t[t[rt].c[1]].R;else t[rt].R = rt;

		return;

	}

	I void rotate(int x)

	{

		register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		maintain(y);maintain(x);

		return;

	}

	stack<int> s;

	I void splay(int x)

	{

		s.push(x);

		for(register int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

		while(!s.empty()){pushdown(s.top());s.pop();}

		while(!isroot(x))

		{

			register int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	I void access(int k)

	{

		for(register int i = 0;k;i = k,k = t[k].fa)

		{

			splay(k);

			pushdown(t[k].c[1]);

			if(t[k].c[1])DFN::change(t[t[k].c[1]].L,1);

			t[k].c[1] = i;

			pushdown(t[k].c[1]);

			if(t[k].c[1])DFN::change(t[t[k].c[1]].L,-1);

			maintain(k);

		}

		return;

	}

	I void makeroot(int k)

	{

		access(k);

		splay(k);

		t[k].rev ^= 1;

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i < n;++i)DFN::add(rd(),rd());

	ST::build(ST::root,1,n);

	DFN::build();

	for(register int i = 1;i <= n;++i)

	{

		LCT::t[i].fa = DFN::f[i][0];

		ST::add(ST::root,DFN::rnk[i],DFN::rnk[i],DFN::dep[i],1,n);

		LCT::t[i].L = LCT::t[i].R = i;

	}

	register char c[20];

	register int x;

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

	{

		scanf("%s",c + 1);x = rd();

		if(c[3] == 'Q')

		{

			printf("%.10lf\n",(double)DFN::query(x) / DFN::calcsiz(x));

		}

		if(c[3] == 'L')

		{

			LCT::access(x);

		}

		if(c[3] == 'C')

		{

			LCT::makeroot(x);

			DFN::root = x;

		}

	}

	return 0;

}