http://www.lydsy.com/JudgeOnline/problem.php?id=3779
有一棵树，初始每个节点有不同的颜色
操作1：根节点到x的路径上的点 染上一种没有出现过的颜色
操作2：操作1后把x换成根
操作3：定义点x的点权为x到根节点路径上不同颜色的数量，查询x的子树点权和
LCT+线段树+dfs序
dfs一遍得到每个点的dfs序，
以及每个点子树的dfs序范围,记点x的子树dfs序范围为 [Lx,Rx]
线段树以dfs序为顺序维护
操作1就是access，
一条Preferred Path 上所有点的颜色相同
在轻重链交换的时候才会涉及到点权的修改
如果lct上父节点x和子节点y之间的边由重链变轻链，那么lct上 以子节点y为根的子树的所有点 的点权减1
实现就是找到t的Auxiliary Tree 上深度最小的点z， 区间[Lz,Rz] 减1
如果lct上父节点x和子节点y之间的边由轻链变重链，那么lct上 以子节点y为根的子树的所有点 的点权加1
实现就是找到t的Auxiliary Tree 上深度最小的点z， 区间[Lz,Rz] 加1
操作2就是LCT的换根操作
不用刻意的去维护换根对线段树的影响，因为换根之前会执行操作1，access
点到新的根节点路径上的颜色数量 就等于 点到原来根节点路径上的颜色数量
查询操作：
分析点x和根节点root 子树的包含关系
若x==root，那就是查询整棵树
若x在root的子树内，直接查x的子树
若root在x的子树内，设root在x的子节点p的子树内，那就是查询整棵树除去p的子树的部分
查询子树就是 线段树按dfs序维护的一段连续的区间
#include<cmath>
#include<cstdio>
#include<iostream> #define N 100001 using namespace std; typedef long long LL; int n;
int front[N],to[N<<],nxt[N<<],tot; int id[N],dy[N],lst[N],tim;
int dep[N];
int lim,F[N][]; int fa[N],ch[N][],root;
bool rev[N]; LL sum[N<<];
int siz[N<<],tag[N<<]; int st[N],top; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
} void dfs(int x)
{
id[x]=++tim;
dy[tim]=x;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
dep[to[i]]=dep[x]+;
F[to[i]][]=x;
fa[to[i]]=x;
dfs(to[i]);
}
lst[x]=tim;
} void build(int k,int l,int r)
{
siz[k]=r-l+;
if(l==r)
{
sum[k]=dep[dy[l]];
return;
}
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
sum[k]=sum[k<<]+sum[k<<|];
} void tagging(int k,int w)
{
sum[k]+=w*siz[k];
tag[k]+=w;
} void push_down(int k)
{
tagging(k<<,tag[k]);
tagging(k<<|,tag[k]);
tag[k]=;
} void change(int k,int l,int r,int opl,int opr,int w)
{
if(l>=opl && r<=opr)
{
tagging(k,w);
return;
}
if(tag[k]) push_down(k);
int mid=l+r>>;
if(opl<=mid) change(k<<,l,mid,opl,opr,w);
if(opr>mid) change(k<<|,mid+,r,opl,opr,w);
sum[k]=sum[k<<]+sum[k<<|];
} void Change(int x,int w)
{
if(x==root) change(,,n,,n,w);
else if(id[root]>id[x] && id[root]<=lst[x])
{
int t=root,c=dep[root]-dep[x]-;
for(int i=lim;i>=;--i)
if(c&(<<i)) t=F[t][i];
if(id[t]>) change(,,n,,id[t]-,w);
if(lst[t]<n) change(,,n,lst[t]+,n,w);
}
else change(,,n,id[x],lst[x],w);
} LL query(int k,int l,int r,int opl,int opr)
{
if(l==opl && r==opr) return sum[k];
if(tag[k]) push_down(k);
int mid=l+r>>; LL res=;
if(opl<=mid) res+=query(k<<,l,mid,opl,min(mid,opr));
if(opr>mid) res+=query(k<<|,mid+,r,max(mid+,opl),opr);
return res;
} double Query(int x)
{
if(x==root) return 1.0*query(,,n,,n)/n;
else if(id[root]>id[x] && id[root]<=lst[x])
{
int t=root,c=dep[root]-dep[x]-;
for(int i=lim;i>=;--i)
if(c&(<<i)) t=F[t][i];
int siz=id[t]-+n-lst[t];
LL res=;
if(id[t]>) res+=query(,,n,,id[t]-);
if(lst[t]<n) res+=query(,,n,lst[t]+,n);
return 1.0*res/siz;
}
return 1.0*query(,,n,id[x],lst[x])/(lst[x]-id[x]+);
} void down(int x)
{
rev[x]^=;
if(ch[x][]) rev[ch[x][]]^=;
if(ch[x][]) rev[ch[x][]]^=;
std::swap(ch[x][],ch[x][]);
} bool isroot(int x)
{
return ch[fa[x]][]!=x && ch[fa[x]][]!=x;
} bool getson(int x)
{
return ch[fa[x]][]==x;
} void rotate(int x)
{
int y=fa[x],z=fa[y];
bool k=ch[y][]==x;
if(!isroot(y)) ch[z][ch[z][]==y]=x;
ch[y][k]=ch[x][k^]; ch[x][k^]=y;
fa[y]=x; fa[x]=z; fa[ch[y][k]]=y;
} void splay(int x)
{
st[top=]=x;
for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
for(int i=top;i;--i)
if(rev[st[i]]) down(st[i]);
int y;
while(!isroot(x))
{
y=fa[x];
if(!isroot(y)) rotate(getson(x)==getson(y) ? y : x);
rotate(x);
}
} int find_root(int x)
{
if(rev[x]) down(x);
while(ch[x][])
{
x=ch[x][];
if(rev[x]) down(x);
}
return x;
} void access(int x)
{
int t=;
while(x)
{
splay(x);
if(ch[x][]) Change(find_root(ch[x][]),);
ch[x][]=t;
if(t) Change(find_root(t),-);
t=x; x=fa[x];
}
} void maker_root(int x)
{
access(x);
splay(x);
rev[x]^=;
root=x;
} int main()
{
freopen("recompile.in", "r", stdin);
freopen("recompile.out", "w", stdout);
int m;
read(n); read(m);
int u,v;
for(int i=;i<n;++i)
{
read(u); read(v);
add(u,v);
}
dep[]=;
dfs();
lim=log(n)/log();
for(int j=;j<=lim;++j)
for(int i=;i<=n;++i)
F[i][j]=F[F[i][j-]][j-];
build(,,n);
root=;
char c[]; int x;
while(m--)
{
scanf("%s",c);
read(x);
if(c[]=='L') access(x);
else if(c[]=='C') maker_root(x);
else printf("%.10lf\n",Query(x));
}
}