Description
Link.
Given is a tree. Every node initially has a color which is different from others'. (called $col_{x}$)
Def: $\text{dis}(x,y)$: the number of different colors on the simple path between x and y.
Supporting the following operations:
RELEASE x: For each $y$ on $\text{path}(x,rt)$, make $col_{y}$=a new color which doesn't exist before.RECENTER x: Make $x$ become the new root after running RELEASE x.REQUEST x: Print: for each $y$ in $\text{subtree}(x)$, the sum of $\text{dis}(y,rt)$ divided the number of nodes in $\text{subtree}(x)$.
Solution
Link Cut Tree.
We can know that $\text{dis}(x,rt)$ is the number of Fake Edges on $\text{path}(x,rt)$ pluses one.
If we change a Real Edge $(u,v)$, where $dep_{u}<dep_{v}$ into a Fake Edge, for each node $x$ in $\text{subtree}(v)$, $\text{dis}(x,rt)$ will be decreased by $1$.
Vice versa.
In order to support such operation: decrease the subtree by $1$, we can fix the DFS order of the given tree.
However, we also need to change the root. How can we fix the DFS order of the given tree?
Let's have a discussion. Denote $x$ for the current operating node, $rt$ for the current root.
- if $rt=x$: modify the whole tree directly.
- if $rt$ isn't in $\text{subtree}(x)$: modify $\text{subtree}(x)$.
- if $rt$ is in $\text{subtree}(x)$: modify $\text{subtree}(x)$ and cancel the modfication of $\text{subtree}(rt)$
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> e[100010];
int n,m,indfn[100010],outdfn[100010],sjc,fa[100010][20],dep[100010],rtnow=1;
#define check(x,f) ((indfn[x]<indfn[f])|(indfn[x]>outdfn[f])) // check whether x isn't in subtree(f)
void dfs(int x,int las)
{
dep[x]=dep[las]+1,fa[x][0]=las,indfn[x]=++sjc;
for(int i=1;i^20;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(unsigned int i=0;i<e[x].size();++i) if(e[x][i]^las) dfs(e[x][i],x);
outdfn[x]=sjc;
}
int getkth(int x,int k)
{
if(k==0) return x;
else
{
for(int i=0;i^20;++i) if((k>>i)&1) x=fa[x][i];
return x;
}
}
struct LinearTree
{
struct node
{
LL val,tag;
}nodes[400010];
void turn(int x,int l,int r)
{
if(nodes[x].tag)
{
int mid=(l+r)>>1;
nodes[x<<1].val+=(mid-l+1)*nodes[x].tag;
nodes[x<<1|1].val+=(r-mid)*nodes[x].tag;
nodes[x<<1].tag+=nodes[x].tag;
nodes[x<<1|1].tag+=nodes[x].tag;
nodes[x].tag=0;
}
}
void ins(int l,int r,int x,int fr,int ba,int val)
{
if(fr>ba||l>ba||r<fr) return;
if(l>=fr&&r<=ba) nodes[x].val+=(r-l+1)*val,nodes[x].tag+=val;
else
{
int mid=(l+r)>>1;
turn(x,l,r);
ins(l,mid,x<<1,fr,ba,val);
ins(mid+1,r,x<<1|1,fr,ba,val);
nodes[x].val=nodes[x<<1].val+nodes[x<<1|1].val;
}
}
LL find(int l,int r,int x,int fr,int ba)
{
if(fr>ba||l>ba||r<fr) return 0;
if(l>=fr&&r<=ba) return nodes[x].val;
else
{
int mid=(l+r)>>1;
turn(x,l,r);
return find(l,mid,x<<1,fr,ba)+find(mid+1,r,x<<1|1,fr,ba);
}
}
void modify(int x,LL val)
{
if(rtnow==x) ins(1,n,1,1,n,val);
else if(check(rtnow,x)) ins(1,n,1,indfn[x],outdfn[x],val);
else
{
int tmp=getkth(rtnow,dep[rtnow]-dep[x]-1);
ins(1,n,1,1,indfn[tmp]-1,val);
ins(1,n,1,outdfn[tmp]+1,n,val);
}
}
}lrt;
struct LinkCutTree
{
#define wis(x) (nodes[nodes[x].fa].ch[1]==(x))
#define isrt(x) ((nodes[nodes[x].fa].ch[0]^(x))&&(nodes[nodes[x].fa].ch[1]^(x)))
struct node
{
int ch[2],fa;
bool rev;
}nodes[100010];
void turn_down(int x)
{
if(nodes[x].rev)
{
swap(nodes[x].ch[0],nodes[x].ch[1]);
if(nodes[x].ch[0]) nodes[nodes[x].ch[0]].rev^=1;
if(nodes[x].ch[1]) nodes[nodes[x].ch[1]].rev^=1;
nodes[x].rev=0;
}
}
void turn_whole(int x)
{
if(!isrt(x)) turn_whole(nodes[x].fa);
turn_down(x);
}
void rotate(int x)
{
int f=nodes[x].fa,ff=nodes[f].fa,t=wis(x);
nodes[x].fa=ff;
if(!isrt(f)) nodes[ff].ch[wis(f)]=x;
nodes[f].ch[t]=nodes[x].ch[t^1];
nodes[nodes[x].ch[t^1]].fa=f;
nodes[x].ch[t^1]=f;
nodes[f].fa=x;
}
void splay(int x)
{
turn_whole(x);
while(!isrt(x))
{
int f=nodes[x].fa;
if(!isrt(f)) rotate((wis(x)^wis(f))?x:f);
rotate(x);
}
}
int findleft(int x)
{
turn_down(x);
while(nodes[x].ch[0]) x=nodes[x].ch[0],turn_down(x);
return x;
}
void access(int x)
{
for(int y=0;x;y=x,x=nodes[x].fa)
{
splay(x);
if(nodes[x].ch[1]) lrt.modify(findleft(nodes[x].ch[1]),1);
if(y) lrt.modify(findleft(y),-1);
nodes[x].ch[1]=y;
}
}
void makert(int x){access(x),splay(x),nodes[x].rev^=1;}
}lct;
char opt[20];
int opx;
template<typename T>
void read(T &hhh)
{
T x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
if(~f) hhh=x;
else hhh=-x;
}
int main()
{
read(n),read(m);
for(int i=1,x,y;i<n;++i)
{
read(x),read(y);
e[x].emplace_back(y);
e[y].emplace_back(x);
}
dfs(1,0);
for(int i=1;i<=n;++i) lrt.ins(1,n,1,indfn[i],indfn[i],dep[i]),lct.nodes[i].fa=fa[i][0];
while(m--)
{
scanf("%s",opt),read(opx);
if(strcmp(opt,"RELEASE")==0) lct.access(opx);
else if(strcmp(opt,"RECENTER")==0) lct.makert(opx),rtnow=opx;
else
{
if(rtnow==opx) printf("%.10f\n",double(lrt.find(1,n,1,1,n))/n);
else if(check(rtnow,opx)) printf("%.10f\n",double(lrt.find(1,n,1,indfn[opx],outdfn[opx]))/(outdfn[opx]-indfn[opx]+1));
else
{
int tmp=getkth(rtnow,dep[rtnow]-dep[opx]-1);
printf("%.10f\n",double(lrt.find(1,n,1,1,indfn[tmp]-1)+lrt.find(1,n,1,outdfn[tmp]+1,n))/(indfn[tmp]+n-outdfn[tmp]-1));
}
}
}
return 0;
}
