题目大意
1、将x到当前根路径上的所有点染成一种新的颜色；
2、将x到当前根路径上的所有点染成一种新的颜色，并且把这个点设为新的根；
3、查询以x为根的子树中所有点权值的平均值。
分析
原题codechef ,Gangsters of Treeland
那题没有换根操作
用神转化把问题转操作1转化成access操作
操作3转化成每个点到根上有多少条虚边
用dfn序+线段树维护
现在多了个换根操作，只是线段树上加个分类讨论而已
注意
longdouble会Wa，double就A了
姿势
1.用dfn序判断x是否y的祖先
bool ispre(int x,int y){
if(x==y) return 0;//相等时不是祖先
return bg[x]<=bg[y]&&ed[y]<=ed[x];
}
2.分类讨论姿势
xxx(int x){
if(x==rt) xxx;
else if(ispre(x,rt)){
xxx;
}
else{
xxx;
}
}
3.多种数据结构时，用类似 seg_mdf()这样加前缀和下划线的方法
4.以后splay打翻转标记时就把儿子换了吧
5.可用注释分割代码
solution
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long LL;
const int M=100007;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
int n,m,rt;
int g[M],te;
struct edge{
int y,nxt;
}e[M<<1];
void addedge(int x,int y){
e[++te].y=y;e[te].nxt=g[x];g[x]=te;
}
//////////////////////////////// split tree
int top[M],pre[M];
int bg[M],ed[M],tdfn;
int dep[M],sz[M];
int son[M],pid[M];
bool ispre(int x,int y){
if(x==y) return 0;//*************
return bg[x]<=bg[y]&&ed[y]<=ed[x];
}
void dfs1(int x){
sz[x]=1;
int p,y;
for(p=g[x];p;p=e[p].nxt)
if((y=e[p].y)!=pre[x]){
pre[y]=x;
dep[y]=dep[x]+1;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
void dfs2(int x){
bg[x]=++tdfn;
pid[tdfn]=x;
if(son[x]){
top[son[x]]=top[x];
dfs2(son[x]);
}
int p,y;
for(p=g[x];p;p=e[p].nxt)
if((y=e[p].y)!=pre[x]&&y!=son[x]){
top[y]=y;
dfs2(y);
}
ed[x]=tdfn;
}
int jump(int x,int to){
for(;dep[top[x]]>dep[to];x=pre[x]){
x=top[x];
if(pre[x]==to) return x;
}
return pid[bg[to]+1];
}
LL getsz(int x){
if(x==rt) return n;
if(ispre(x,rt)){
int y=jump(rt,x);
return n-sz[y];
}
else{
return sz[x];
}
}
////////////////////////////////// Segment
struct Seg{
LL sum,tag;
}c[M<<2];
void seg_pushup(int x){
c[x].sum=c[x<<1].sum+c[x<<1|1].sum;
}
void seg_totag(int x,LL d,LL len){
c[x].sum+=d*len;
c[x].tag+=d;
}
void seg_pushdown(int x,LL aa,LL bb){
if(c[x].tag){
seg_totag(x<<1,c[x].tag,aa);
seg_totag(x<<1|1,c[x].tag,bb);
c[x].tag=0;
}
}
void seg_mdf(int x,int l,int r,int tl,int tr,LL d){
if(tl<=l&&r<=tr){
seg_totag(x,d,r-l+1);
return;
}
int mid=l+r>>1;
seg_pushdown(x,mid-l+1,r-mid);
if(tl<=mid) seg_mdf(x<<1,l,mid,tl,tr,d);
if(mid<tr) seg_mdf(x<<1|1,mid+1,r,tl,tr,d);
seg_pushup(x);
}
void seg_add(int x,LL d){
if(x==rt) return seg_totag(1,d,tdfn);
if(ispre(x,rt)){
int y=jump(rt,x);
seg_mdf(1,1,tdfn,bg[1],ed[1],d);
seg_mdf(1,1,tdfn,bg[y],ed[y],-d);
}
else{
seg_mdf(1,1,tdfn,bg[x],ed[x],d);
}
}
LL seg_get(int x,int l,int r,int tl,int tr){
if(tl<=l&&r<=tr) return c[x].sum;
int mid=l+r>>1;
seg_pushdown(x,mid-l+1,r-mid);
LL res=0;
if(tl<=mid) res+=seg_get(x<<1,l,mid,tl,tr);
if(mid<tr) res+=seg_get(x<<1|1,mid+1,r,tl,tr);
return res;
}
LL seg_sum(int x){
if(x==rt) return c[1].sum;
LL res=0;
if(ispre(x,rt)){
int y=jump(rt,x);
res+=seg_get(1,1,tdfn,bg[1],ed[1]);
res-=seg_get(1,1,tdfn,bg[y],ed[y]);
}
else{
res=seg_get(1,1,tdfn,bg[x],ed[x]);
}
return res;
}
/////////////////////////////////////// LCT
struct LCT{
int ch[2],p,rev;
int id,lf,rt;//**********************************
void init(int ii){
ch[0]=ch[1]=p=rev=0;
lf=rt=id=ii;
}
}a[M];
int stack[M],tot;
void torev(int x){
a[x].rev^=1;
swap(a[x].ch[0],a[x].ch[1]);//****
swap(a[x].lf,a[x].rt);
}
void pushup(int x){
a[x].lf=a[x].rt=a[x].id;
if(a[x].ch[0]) a[x].lf=a[a[x].ch[0]].lf;
if(a[x].ch[1]) a[x].rt=a[a[x].ch[1]].rt;
}
void pushdown(int x){
if(a[x].rev){
if(a[x].ch[0]) torev(a[x].ch[0]);
if(a[x].ch[1]) torev(a[x].ch[1]);
a[x].rev^=1;
}
}
bool isrt(int x){
int y=a[x].p;
return a[y].ch[0]!=x&&a[y].ch[1]!=x;
}
void clear(int x){
for(;!isrt(x);x=a[x].p) stack[++tot]=x;
for(stack[++tot]=x;tot>0;tot--) pushdown(stack[tot]);
}
void rot(int x){
int y=a[x].p;
int z=a[y].p;
int D=a[y].ch[1]==x,ss=D^1;
if(!isrt(y)) a[z].ch[a[z].ch[1]==y]=x;
a[x].p=z;
a[y].p=x;
if(a[x].ch[ss]) a[a[x].ch[ss]].p=y;
a[y].ch[D]=a[x].ch[ss];
a[x].ch[ss]=y;
pushup(y);
pushup(x);
}
void splay(int x){
int y,z;
for(clear(x);!isrt(x);rot(x)){
y=a[x].p;
z=a[y].p;
if(isrt(y)) continue;
if((a[y].ch[1]==x)!=(a[z].ch[1]==y)) rot(x);
else rot(y);
}
}
void access(int x){
for(int t=0;x;t=x,x=a[x].p){
splay(x);
if(a[x].ch[1]) seg_add(a[a[x].ch[1]].lf,1);
if(t) seg_add(a[t].lf,-1);
a[x].ch[1]=t;
pushup(x);
}
}
void ac(int x){
access(x);
splay(x);
}
void chgrt(int x){
ac(x);
torev(x);
}
///////////////////////////// main
int main(){
int i,x,y;
n=rd(),m=rd();rt=1;
for(i=1;i<n;i++){
x=rd(),y=rd();
addedge(x,y);
addedge(y,x);
}
pre[1]=0;
dep[1]=1;
dfs1(1);
top[1]=1;
dfs2(1);
for(i=1;i<=n;i++){
a[i].init(i);
if(pre[i]){
a[i].p=pre[i];
seg_add(i,1);
}
}
char s[13];
while(m--){
scanf("%s",s);
x=rd();
if(s[2]=='L'){
ac(x);
}
else if(s[2]=='C'){
chgrt(x);
rt=x;
}
else{
LL tp1=seg_sum(x);
LL tp2=getsz(x);
tp1+=tp2;
printf("%.10lf\n",(db)tp1/(db)tp2);
}
}
return 0;
}