题面
escription
黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有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操作的存在，这个集合并不一定是始终不变的。
至此，安全机构认为已经不需要实际的实验了，于是他们拜托你编写一个程序，模拟实验的结果，并回答所有的询问。
Input
输入的第一行包含两个整数n和m，分别代表局域网中计算机的数量，以及操作和询问的总数。
接下来n-1行，每行包含两个整数x和y，表示局域网中编号为x和y的计算机之间有网线直接相连。
接下来m行，每行包含一个操作或者询问，格式如问题描述中所述。
Output
对于每个询问，输出一个实数，代表平均感染时间。输出与答案的绝对误差不超过 10^(-6)时才会被视为正确。
Sample Input
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
Sample Output
4.0000000000
2.0000000000
1.3333333333
HINT
N < = 1 00 000 M < = 1 00 000
解题思路
数据结构恶心题。发现病毒的传播和(lct)的(access)很像，如果虚边变成实边就让这个边权变为(0)，实边变成虚边就让这个边权变为(1)，然后我们用线段树维护一下，线段树下标为(dfs)序。然后对于换根就直接(makeroot)，对于询问要分类讨论一下。和(BZOJ 3083)很像。最后注意修改的时候要记录一下深度最浅的点，就是每个(splay)的根，从根进行修改。这题要(long) (long)，多年(oi)一场空，不开(long) (long)见祖宗 ，写的时候见了祖宗了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int MAXN = 200005;
typedef long long LL;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],ll[MAXN],rr[MAXN],Fa[MAXN];
int dep[MAXN],wt[MAXN],fa[MAXN],son[MAXN],top[MAXN];
int siz[MAXN],sum[MAXN<<2],lazy[MAXN<<2],in[MAXN],out[MAXN],rt,num;
bool tag[MAXN];
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
void dfs1(int x,int f,int d){
dep[x]=d;fa[x]=f;siz[x]=1;ll[x]=rr[x]=x;
in[x]=++num;wt[num]=d;Fa[x]=f;
int maxson=-1,u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==f) continue;
dfs1(u,x,d+1);siz[x]+=siz[u];
if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}
}out[x]=num;
}
void dfs2(int x,int topf){
top[x]=topf;
if(!son[x]) return;dfs2(son[x],topf);int u;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==fa[x] || u==son[x]) continue;
dfs2(u,u);
}
}
void build(int x,int l,int r){
if(l==r){
sum[x]=wt[l];return ;
}
int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);
sum[x]=sum[x<<1]+sum[x<<1|1];
}
inline void pushdown(int x,int ln,int rn){
sum[x<<1]+=ln*lazy[x];sum[x<<1|1]+=rn*lazy[x];
lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x];lazy[x]=0;
}
inline void update(int x,int l,int r,int L,int R,int k){
if(R<L) return;
if(L<=l && r<=R) {
sum[x]+=(r-l+1)*k;lazy[x]+=k;return;
}
int mid=(l+r)>>1;if(lazy[x]) pushdown(x,mid-l+1,r-mid);
if(L<=mid) update(x<<1,l,mid,L,R,k);
if(mid<R) update(x<<1|1,mid+1,r,L,R,k);
sum[x]=sum[x<<1]+sum[x<<1|1];
}
LL query(int x,int l,int r,int L,int R){
if(R<L) return 0;
if(L<=l && r<=R) return sum[x];
int mid=(l+r)>>1;LL ret=0;if(lazy[x]) pushdown(x,mid-l+1,r-mid);
if(L<=mid) ret+=query(x<<1,l,mid,L,R);
if(mid<R) ret+=query(x<<1|1,mid+1,r,L,R);
return ret;
}
inline int findson(int x,int y){
while(top[x]!=top[y]){
if(Fa[top[x]]==y) return top[x];
x=Fa[top[x]];
}
return son[y];
}
inline void updSon(int x,int k){
if(x==rt) update(1,1,n,1,n,k);
else if(in[x]>=in[rt] || out[x]<out[rt]) update(1,1,n,in[x],out[x],k);
else {
int now=findson(rt,x);
update(1,1,n,1,in[now]-1,k);update(1,1,n,out[now]+1,n,k);
}
}
inline LL qSon(int x){
if(x==rt) return query(1,1,n,1,n);
else if(in[x]>=in[rt] || out[x]<out[rt]) return query(1,1,n,in[x],out[x]);
else {
int now=findson(rt,x);
return query(1,1,n,1,in[now]-1)+query(1,1,n,out[now]+1,n);
}
}
inline int qSiz(int x){
if(x==rt) return n;
else if(in[x]>=in[rt] || out[x]<out[rt]) return siz[x];
return n-siz[findson(rt,x)];
}
namespace lct{
int ch[MAXN][2];
inline bool isroot(int x){
return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);
}
inline bool check(int x){
return (x==ch[fa[x]][1]);
}
inline void pushup(int x){
if(!ch[x][0]) ll[x]=x;
else ll[x]=ll[ch[x][0]];
if(!ch[x][1]) rr[x]=x;
else rr[x]=rr[ch[x][1]];
}
inline void pushdown(int x){
if(tag[x]){
tag[ch[x][0]]^=1;tag[ch[x][1]]^=1;
swap(ll[ch[x][0]],rr[ch[x][0]]);
swap(ll[ch[x][1]],rr[ch[x][1]]);tag[x]^=1;
swap(ch[x][0],ch[x][1]);
}
}
void pd(int x) {if(!isroot(x)) pd(fa[x]);pushdown(x);}
inline void rotate(int x){
int y=fa[x],z=fa[y];bool chk=check(x);
if(!isroot(y)) ch[z][check(y)]=x;
ch[y][chk]=ch[x][chk^1];fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);
}
inline void splay(int x){
pd(x);
for(;!isroot(x);rotate(x))
if(!isroot(fa[x])) rotate(check(x)==check(fa[x])?fa[x]:x);
}
inline void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);if(y) updSon(ll[y],-1);
if(ch[x][1]) updSon(ll[ch[x][1]],1);
ch[x][1]=y;pushup(x);
}
}
inline void makeroot(int x){
access(x);splay(x);tag[x]^=1;
swap(ll[x],rr[x]);
}
}
signed main(){
// freopen("19.in","r",stdin);
// freopen("my.out","w",stdout);
n=rd(),m=rd();int x,y;char s[10];LL z;
for(int i=1;i<n;i++) {
x=rd(),y=rd();
add(x,y),add(y,x);
}
dfs1(1,0,1);dfs2(1,1);build(1,1,n);rt=1;
while(m--){
scanf("%s",s+1);x=rd();
if(s[3]=='L') lct::access(x);
if(s[3]=='C') lct::makeroot(x),rt=x;
if(s[3]=='Q') {
y=qSiz(x);z=qSon(x);
printf("%.10lf
",(double)z/y);
}
}
return 0;
}