Codechef 13.11MONOPLOY LCT+树链剖分+线段树

题解：

我分到的集训队作业的A，傻逼数据结构题。

注意到每次操作就是将这个点Access一下，同时这个点需要跨越的国家数就是走过的虚边数。

那么考虑子树内部所有点走过虚边数目之和。

子树内的每条虚边，不妨设为i的父亲边，会产生$siz_i$的贡献。

假设询问的是x，求出子树内所有虚边的贡献，求完平均值之后再加上x到根的路径上有多少虚边就行了。

每次Access的时候用树链剖分维护实虚边的切换。

时间复杂度$O(nlog^2n)$。

代码：

目前在CC上rank1，然并卵。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x+1;
}
char getch(){
	char c;
	while((c=getc())!='O'&&c!='q');
	return c;
}

#define N 100010
int head[N],next[N<<1],end[N<<1],ind;
void addedge(int a,int b){
	int q=++ind;
	end[q]=b;
	next[q]=head[a];
	head[a]=q++;
}
void make(int a,int b){
	addedge(a,b);
	addedge(b,a);
}

int siz[N],son[N],pa[N],dep[N];
void dfs1(int x,int fa){
	siz[x]=1;
	int mx=-1;
	for(int j=head[x];j;j=next[j])
		if(end[j]!=fa){
			dep[end[j]]=dep[x]+1;
			pa[end[j]]=x;
			dfs1(end[j],x);
			siz[x]+=siz[end[j]];
			if(siz[end[j]]>mx){
				mx=siz[end[j]];
				son[x]=end[j];
			}
		}
}

int p_id[N],id_p[N],top[N],id;
void dfs2(int x,int Top){
	top[x]=Top;
	p_id[x]=++id;
	id_p[id]=x;
	if(son[x])
		dfs2(son[x],Top);
	for(int j=head[x];j;j=next[j])
		if(end[j]!=pa[x]&&end[j]!=son[x])
			dfs2(end[j],end[j]);
}

struct SegmentTree{
	ll a[262144],b[262144],M;
	void init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		for(int i=1;i<(M<<1);++i)
			a[i]=b[i]=0;
		for(int i=2;i<=_siz;++i){
			a[M+i]=1;
			b[M+i]=siz[id_p[i]];
		}
		for(int i=M-1;i>=1;--i){
			a[i]=a[i<<1]+a[i<<1^1];
			b[i]=b[i<<1]+b[i<<1^1];
		}
	}
	ll qa(int tl,int tr){
		if(tl>tr)
			return 0;
		ll re=0;
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)
				re+=a[tl^1];
			if(tr&1)
				re+=a[tr^1];
		}
		return re;
	}
	ll qb(int tl,int tr){
		if(tl>tr)
			return 0;
		ll re=0;
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)
				re+=b[tl^1];
			if(tr&1)
				re+=b[tr^1];
		}
		return re;
	}
	void ma(int x,int v){
		for(a[x+=M]=v,x>>=1;x;x>>=1)
			a[x]=a[x<<1]+a[x<<1^1];
	}
	void mb(int x,int v){
		for(b[x+=M]=v,x>>=1;x;x>>=1)
			b[x]=b[x<<1]+b[x<<1^1];
	}
}Seg;

#define ls ch[0]
#define rs ch[1]
#define inf 0x3f3f3f3f
typedef pair<int,int> pii;
#define mp make_pair
struct Node{
	Node*ch[2],*pa;
	pii mn;
	int id;
	Node():mn(mp(inf,inf)),id(inf){}
	
	bool d(){
		return this==pa->rs;
	}
	void sc(Node*p,bool d){
		ch[d]=p;
		p->pa=this;
	}
	void up();
	bool isroot();
}mem[N],*P,Tnull,*null=&Tnull,*ins[N];
Node*newnode(){
	++P;
	P->ls=P->rs=P->pa=null;
	P->id=P-mem;
	P->mn=mp(dep[P->id],P->id);
	return P;
}
void Node::up(){
	mn=mp(dep[id],id);
	if(ls!=null)
		mn=min(mn,ls->mn);
	if(rs!=null)
		mn=min(mn,rs->mn);
}
bool Node::isroot(){
	return pa==null||(this!=pa->ls&&this!=pa->rs);
}

void Rot(Node*p){
	bool d=p->d();
	Node*fa=p->pa;
	fa->sc(p->ch[!d],d);
	fa->up();
	p->pa=fa->pa;
	if(!fa->isroot())
		fa->pa->ch[fa->d()]=p;
	p->sc(fa,!d);
}
void Splay(Node*p){
	while(!p->isroot()){
		if(p->pa->isroot())
			Rot(p);
		else
			Rot(p->d()==p->pa->d()?p->pa:p),Rot(p);
	}
	p->up();
}

void Access(Node*p){
	Node*q=null;
	while(p!=null){
		Splay(p);
		if(p->rs!=null){
			Seg.ma(p_id[p->rs->mn.second],1);
			Seg.mb(p_id[p->rs->mn.second],siz[p->rs->mn.second]);
		}
		if(q!=null){
			Seg.ma(p_id[q->mn.second],0);
			Seg.mb(p_id[q->mn.second],0);
		}
		p->sc(q,1);
		p->up();
		q=p;
		p=p->pa;
	}
}

void reset(){
	ind=0;
	memset(head,0,sizeof head);
	memset(son,0,sizeof son);
	id=0;
	P=mem;
}

int query(int x){
	int re=0;
	while(top[x]!=1){
		re+=Seg.qa(p_id[top[x]],p_id[x]);
		x=pa[top[x]];
	}
	return re+Seg.qa(p_id[1],p_id[x]);
}
int main(){
//#ifndef ONLINE_JUDGE
//	freopen("tt.in","r",stdin);
//#endif
	int T=getint()-1,n,a,b,i,j,q,x;
	char ch;
	while(T--){
		reset();
		n=getint()-1;
		for(i=1;i<n;++i){
			a=getint();
			b=getint();
			make(a,b);
		}
		dep[1]=1;
		dfs1(1,-1);
		dfs2(1,1);
		for(i=1;i<=n;++i)
			ins[i]=newnode();
		for(i=2;i<=n;++i)
			ins[i]->pa=ins[pa[i]];
		Seg.init(n);
		
		for(q=getint()-1;q;q--){
			ch=getch();
			if(ch=='O')
				Access(mem+getint());
			else{
				x=getint();
				printf("%.10lf\n",((double)Seg.qb(p_id[x]+1,p_id[x]+siz[x]-1)/siz[x])+query(x));
			}
		}
	}
	
	return 0;
}