一个点的感染时间为它到根路径上虚边数+1。
用Link-Cut Tree模拟虚实边切换，每次切换时等价于在一段或两段DFS序区间更新，线段树维护即可。
时间复杂度$O(n\log^2n)$。
#include<cstdio>
typedef long long ll;
const int N=100010,M=262145;
int n,m,i,x,y,root;
int g[N],nxt[N<<1],v[N<<1],ed;
int top[N],child[N],fa[N],d[N],size[N],st[N],en[N],dfn,seq[N];
inline void addedge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void swap(int&a,int&b){int c=a;a=b;b=c;}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int tag[M];ll val[M];
inline void add1(int x,int a,int b,int p){val[x]+=(ll)(b-a+1)*p;tag[x]+=p;}
inline void pb(int x,int a,int b){
if(tag[x]){
int mid=(a+b)>>1;
add1(x<<1,a,mid,tag[x]),add1(x<<1|1,mid+1,b,tag[x]),tag[x]=0;
}
}
inline void up(int x){val[x]=val[x<<1]+val[x<<1|1];}
void build(int x,int a,int b){
if(a==b){val[x]=seq[a];return;}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);
}
void change(int x,int a,int b,int c,int d,int p){
if(c>d)return;
if(c<=a&&b<=d){add1(x,a,b,p);return;}
pb(x,a,b);
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c,d,p);
if(d>mid)change(x<<1|1,mid+1,b,c,d,p);
up(x);
}
ll ask(int x,int a,int b,int c,int d){
if(c>d)return 0;
if(c<=a&&b<=d)return val[x];
pb(x,a,b);
int mid=(a+b)>>1;ll t=0;
if(c<=mid)t=ask(x<<1,a,mid,c,d);
if(d>mid)t+=ask(x<<1|1,mid+1,b,c,d);
return up(x),t;
}
inline int lca2(int x,int y){
int t;
while(top[x]!=top[y])t=top[x],x=fa[top[x]];
return x==y?t:child[y];
}
inline void subadd(int x,int p){
if(x==root){change(1,1,n,1,n,p);return;}
if(st[x]>st[root]||en[x]<en[root]){change(1,1,n,st[x],en[x],p);return;}
int y=lca2(root,x);
change(1,1,n,1,st[y]-1,p),change(1,1,n,en[y]+1,n,p);
}
inline double query(int x){
if(x==root)return(double)ask(1,1,n,1,n)/n;
if(st[x]>st[root]||en[x]<en[root])return(double)ask(1,1,n,st[x],en[x])/(en[x]-st[x]+1);
int y=lca2(root,x);
return(double)(ask(1,1,n,1,st[y]-1)+ask(1,1,n,en[y]+1,n))/(n-en[y]+st[y]-1);
}
int f[N],son[N][2],a[N];bool rev[N];
inline bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
inline void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}
inline void pb(int x){if(rev[x])rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}
inline void rotate(int x){
int y=f[x],w=son[y][1]==x;
son[y][w]=son[x][w^1];
if(son[x][w^1])f[son[x][w^1]]=y;
if(f[y]){
int z=f[y];
if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;
}
f[x]=f[y];son[x][w^1]=y;f[y]=x;
}
inline void splay(int x){
int s=1,i=x,y;a[1]=i;
while(!isroot(i))a[++s]=i=f[i];
while(s)pb(a[s--]);
while(!isroot(x)){
y=f[x];
if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
rotate(x);
}
}
inline int getson(int x){
pb(x);
while(son[x][0])pb(x=son[x][0]);
return x;
}
inline void access(int x){
for(int y=0;x;y=x,x=f[x]){
splay(x);
if(son[x][1])subadd(getson(son[x][1]),1);
if(y)subadd(getson(y),-1);
son[x][1]=y;
}
}
inline void makeroot(int x){access(x);splay(x);rev1(root=x);}
void dfs1(int x,int pre,int dep){
size[x]=1;d[x]=dep;fa[x]=f[x]=pre;
int heavy=0,sizemax=0,i;
for(i=g[x];i;i=nxt[i])if(v[i]!=pre){
dfs1(v[i],x,dep+1),size[x]+=size[v[i]];
if(size[v[i]]>sizemax)sizemax=size[v[i]],heavy=v[i];
}
if(heavy)child[x]=heavy;
}
void dfs2(int x,int pre,int t){
st[x]=++dfn;seq[dfn]=d[x];top[x]=t;
if(child[x])dfs2(child[x],x,t);
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre&&v[i]!=child[x])dfs2(v[i],x,v[i]);
en[x]=dfn;
}
char op[10];
int main(){
read(n);read(m);
for(i=1;i<n;i++)read(x),read(y),addedge(x,y),addedge(y,x);
dfs1(root=1,0,1);dfs2(1,0,1);
build(1,1,n);
while(m--){
scanf("%s%d",op,&x);
if(op[2]=='L')access(x);
if(op[2]=='C')makeroot(x);
if(op[2]=='Q')printf("%.10f\n",query(x));
}
return 0;
}