神仙题.
题意:
一开始有n个点,每个点有一独特的颜色,根为1,操作如下:
- 1.把点到根的路径上的点的颜色变成一个新的颜色.
- 2.把点到根的路径上的点的颜色变成一个新的颜色,并换根.
- 3.求子树中的点到根的路径上的颜色的颜色总数期望.
由于1.2操作的缘故,所以同一颜色的只能为一条链.
如果把一条链看成一个,那么一个点到根路径上的颜色总数就为access()内循环的次数.
我们把每个点的代价看为内循环的次数(即到根的虚边个数+1)
在的时候,实边变虚边时,子树的所有点的代价+1;虚边变实边时,子树所有点的代价-1.
我们用树状数组维护代价.(其实用线段树更好理解)
(不会用树状数组做区间加、区间求和的请戳这里中的树状数组解法讲解）
为了方便求值，我们先预处理出dfs序。
但需要注意的是，求值要分类讨论：
modify时类似,只是modify的一定不是root.
详见代码:
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g getchar()
#define lc tr[x].son[0]
#define rc tr[x].son[1]
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,fa[N][19],in[N],out[N],ts,dep[N],root,bin[19];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
struct node{int f,son[2];bool v;}tr[N];
struct option{char op;int x;}Q[N];
namespace bit{
ll a[N],b[N];//a维护差分数组的前缀和,b维护差分值乘位置的前缀和
int lowbit(int x){return x&-x;}
void up(int x,int d){for(ll y=1LL*x*d;x<=n;x+=lowbit(x))a[x]+=d,b[x]+=y;}//不写1LL会炸
void change(int l,int r,int d){up(l,d);up(r+1,-d);}//l~r增加d
ll down(int x)
{
ll sum(0);
for(ll y=x+1;x;x-=lowbit(x))sum+=y*a[x]-b[x];
return sum;
}
ll query(int l,int r){return down(r)-down(l-1);}
}
void dfs(int x)
{
in[x]=++ts;
bit::change(in[x],in[x],dep[x]);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y==fa[x][0])continue;
tr[y].f=fa[y][0]=x;for(int i=1;fa[y][i-1];i++)fa[y][i]=fa[fa[y][i-1]][i-1];//求祖宗
dep[y]=dep[x]+1;dfs(y);
}
out[x]=ts;
}
int jump(int x,int y)//x单跳y次
{
for(int i=0;y;i++)if(y&bin[i])y^=bin[i],x=fa[x][i];
return x;
}
void modify(int x,int d)//把x的关键集合的值,都增加d
{
if(!(in[x]<=in[root]&&in[root]<=out[x]))bit::change(in[x],out[x],d);//根不在x的子树内
else
{
x=jump(root,dep[root]-dep[x]-1);//jump(rt,dep[rt]-dep[x]-1)为x的孩子
if(in[x]>1) bit::change(1,in[x]-1,d);//逗比了
if(out[x]<n)bit::change(out[x]+1,n,d);
}
}
double ask(int x)
{
if(x==root)return 1.0*bit::query(1,n)/n;
else if(!(in[x]<=in[root]&&in[root]<=out[x]))
return 1.0*bit::query(in[x],out[x])/(out[x]-in[x]+1);
else
{
int y=jump(root,dep[root]-dep[x]-1);
double s=bit::query(1,in[y]-1);int sz=n-(out[y]-in[y]+1);
if(out[y]<n)s+=bit::query(out[y]+1,n);
return s/sz;
}
}
void fz(int x)
{
tr[x].v=0;swap(lc,rc);
tr[lc].v^=1;tr[rc].v^=1;
}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f,r,R;
r=tr[x].son[w];R=f;tr[R].son[1-w]=r;if(r)tr[r].f=R;
r=x;R=ff;if(tr[R].son[0]==f)tr[R].son[0]=r;else if(tr[R].son[1]==f)tr[R].son[1]=r;tr[r].f=R;
r=f;R=x;tr[R].son[w]=r;tr[r].f=R;
}
bool rt(int x){return tr[tr[x].f].son[0]!=x&&tr[tr[x].f].son[1]!=x;}
void wh(int x)
{
if(!rt(x))wh(tr[x].f);
if(tr[x].v)fz(x);
}
void splay(int x)
{
wh(x);
while(!rt(x))
{
int f=tr[x].f;
if(rt(f))rotate(x,tr[f].son[0]==x);
else
{
int ff=tr[f].f,a=(tr[f].son[0]==x),b=(tr[ff].son[0]==f);
rotate(a^b?x:f,a);rotate(x,b);
}
}
}
int find_root(int x)
{
if(tr[x].v)fz(x);
while(lc)
{
x=lc;
if(tr[x].v)fz(x);
}
return x;
}
void access(int x)
{
for(int y=0;x;x=tr[y=x].f)
{
splay(x);
if(rc)modify(find_root(rc),1);
if(y)modify(find_root(y),-1);
rc=y;//逗比了
}
}
void makeroot(int x)
{
access(x);splay(x);
tr[x].v^=1;root=x;
}
void qr(int &x)
{
char c=g;x=0;
while(!isdigit(c))c=g;
while(isdigit(c))x=x*10+c-'0',c=g;
}
int main()
{
qr(n);qr(m);
bin[0]=1;for(int i=1;bin[i-1]<=n;i++)bin[i]=bin[i-1]<<1;
int x,y;char s[11];
for(int i=1;i<n;i++)
qr(x),qr(y),ins(x,y),ins(y,x);
dep[1]=root=1;dfs(1);
for(int i=1;i<=m;i++)
{
scanf("%s",s);qr(Q[i].x);
switch(s[2]){
case 'L':Q[i].op=1;break;
case 'C':Q[i].op=2;break;
case 'Q':Q[i].op=3;break;
}
}
while(m&&Q[m].op!=3)m--;//后面都是无用功
for(int i=1;i<=m;i++)
{
x=Q[i].x;
switch(Q[i].op){
case 1:access(x);break;
case 2:makeroot(x);break;
case 3:printf("%.10lf
",(ask(x)));break;
}
}
return 0;
}
调试找到的bug: