【BZOJ3779】重组病毒
Description
黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有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台计算机，编号为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行，每行包含一个操作或者询问，格式如问题描述中所述。
接下来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
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
2.0000000000
1.3333333333
HINT
N < = 1 00 000 M < = 1 00 000
题解：出题人简直有毒，给你一大坨文字，然后让你猜这是啥数据结构。实际上，如果你把release看成access，recenter看成makeroot，这tm就是一个LCT。答案是什么？每个点的感染时间就是该点到根路径上虚边的个数。
所以只需要在access的时候维护子树的点权和即可。这个可以用DFS序+树状数组区间修改区间查询。不过有换根操作如何处理子树呢？去做遥远的国度那题吧，然后就很简单了。
注意：splay中的子树与原树中的子树并不相同。所以在access中修改子树信息时，并不是modify(s[x].ch[1])，而是在s[x].ch[1]的子树中找到深度最小的那个点，并modify那个点。并且为了平衡，我们需要再将那个点splay一下。
#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?'
':' ');
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
",getans(a));
//for(j=1;j<=n;j++) printf("%lld%c",getsum(p[j])-getsum(p[j]-1),j==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