3.28 省选模拟赛 染色 LCT+线段树

发现和SDOI2017树点涂色差不多 但是当时这道题模拟赛的时候不会写 赛后也没及时订正 所以这场模拟赛的这道题虽然秒想到了LCT和线段树但是最终还是只是打了暴力。

痛定思痛 还是要把这道题给补了。

但是对于这道题来说 暴力还是有价值的。

考虑20分 每次暴力dfs.

考虑对于树是随机生成的 那么期望高度为logn 我们发现每次修改只用修改到1 也就是说每次暴力修改颜色的话只需要logn的时间复杂度.

考虑如何动态维护子树内的值 考虑修改一个点的颜色 子树内之前和它颜色一样的点 显然子树内部整体答案+1 如果不一样那么没有影响 和当前一样也没有影响。

考虑这个点和它的父亲此时答案是一样的如果原来答案也是一样的 那么没有任何的修改 如果不一样 那么子树内部整体-1.

依靠这个思路我们可以 维护一棵线段树 logn的时间内进行区间修改 区间查询。

考虑100分的做法 发现我们暴力慢的地方在于每次都要向上跳。

有优化的地方是 如果当前点可能树上的一段区间颜色是一样的 我们只需要在 当前修改节点x和那段颜色一样的点y的LCA处修改 剩下的直接向上跳即可。

换个角度 其实这个染颜色其实像是LCT 的ACCESS操作 这样我们就可以很方便的维护上述的操作。

考虑这样做的向上跳的复杂度 可以发现利用LCT的性质 均摊logn.

所以每次在access的时候 完成子树内部的修改即可。维护dfs序线段树 复杂度nlog^2.

const int MAXN=150010;

int n,Q,len,cnt;

int lin[MAXN],c[MAXN][2],f[MAXN],ver[MAXN<<1],nex[MAXN<<1],dfn[MAXN],out[MAXN];

int fa[MAXN],d[MAXN],sz[MAXN],son[MAXN],top[MAXN],v[MAXN];

inline void add(int x,int y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

}

inline void dfs(int x)

{

	sz[x]=1;

	go(x)if(tn^fa[x])

	{

		fa[tn]=x;d[tn]=d[x]+1;

		dfs(tn);

		sz[x]+=sz[tn];

		if(sz[tn]>sz[son[x]])son[x]=tn;

	}

}

inline void dfs(int x,int father)

{

	top[x]=father;dfn[x]=++cnt;v[cnt]=x;

	if(son[x])dfs(son[x],father);

	go(x)if(tn!=fa[x]&&tn!=son[x])dfs(tn,tn);

	out[x]=cnt;

}

inline int LCA(int x,int y)

{

	while(top[x]^top[y])

	{

		if(d[top[x]]<d[top[y]])swap(x,y);

		x=fa[top[x]];

	}

	return d[x]<d[y]?x:y;

}

struct seg{int tag,mx,l,r;ll sum;}t[MAXN<<2];

inline void spread(int p,int v)

{

	tag(p)+=v;mx(p)+=v;

	sum(p)+=(r(p)-l(p)+1)*v;

}

inline void pushdown(int p)

{

	spread(zz,tag(p));

	spread(yy,tag(p));

	tag(p)=0;

}

inline void pushup(int p)

{

	mx(p)=max(mx(zz),mx(yy));

	sum(p)=sum(zz)+sum(yy);

}

inline void build(int p,int l,int r)

{

	l(p)=l;r(p)=r;

	if(l==r){mx(p)=d[v[l]];sum(p)=d[v[l]];return;}

	int mid=(l+r)>>1;

	build(zz,l,mid);build(yy,mid+1,r);

	pushup(p);

}

inline void change(int p,int l,int r,int x)

{

	if(l<=l(p)&&r>=r(p)){spread(p,x);return;}

	int mid=(l(p)+r(p))>>1;

	if(tag(p))pushdown(p);

	if(l<=mid)change(zz,l,r,x);

	if(r>mid)change(yy,l,r,x);

	pushup(p);

}

inline int ask(int p,int x)

{

	if(l(p)==r(p))return mx(p);

	int mid=(l(p)+r(p))>>1;

	if(tag(p))pushdown(p);

	if(x<=mid)return ask(zz,x);

	return ask(yy,x);

}

inline int ask(int p,int l,int r)

{

	if(l<=l(p)&&r>=r(p))return mx(p);

	int mid=(l(p)+r(p))>>1,w=0;

	if(tag(p))pushdown(p);

	if(l<=mid)w=ask(zz,l,r);

	if(r>mid)w=max(w,ask(yy,l,r));

	return w;

}

inline ll asksum(int p,int l,int r)

{

	if(l<=l(p)&&r>=r(p))return sum(p);

	int mid=(l(p)+r(p))>>1;ll w=0;

	if(tag(p))pushdown(p);

	if(l<=mid)w=asksum(zz,l,r);

	if(r>mid)w=w+asksum(yy,l,r);

	return w;

}

inline void asksum(int x)

{

	ll w=asksum(1,dfn[x],out[x]);

	double ans=1.0*w/sz[x];

	printf("%.10lf\n",ans);

}

inline int pd(int x){return c[f[x]][1]==x||c[f[x]][0]==x;}//判断x是否为根.

inline void rotate(int x)

{

	int old=f[x],oldf=f[old],k=c[old][1]==x;

	c[old][k]=c[x][k^1];c[x][k^1]=old;

	if(pd(old))c[oldf][c[oldf][1]==old]=x;

	if(c[old][k])f[c[old][k]]=old;

	f[old]=x;f[x]=oldf;

}

inline void splay(int x)

{

	while(pd(x))

	{

		if(pd(f[x]))rotate((c[f[x]][1]==x)^(c[f[f[x]]][1]==f[x])?x:f[x]);

		rotate(x);

	}

}

inline int findroot(int x)

{

	splay(x);

	while(c[x][0])x=c[x][0];

	splay(x);return x;

}

inline void access(int x)

{

	int y=0;

	while(x)

	{

		splay(x);

		if(c[x][1])

		{

			int w=c[x][1];

			c[x][1]=0;

			w=findroot(w);

			change(1,dfn[w],out[w],1);

		}

		if(y)

		{

			y=findroot(y);

			change(1,dfn[y],out[y],-1);

		}

		c[x][1]=y;

		y=x;x=f[x];

	}

}

int main()

{

	freopen("1.in","r",stdin);

	//freopen("1.out","w",stdout);

	get(n);

	rep(2,n,i)

	{

		int x,y;

		get(x)+1;get(y)+1;

		//cout<<x<<' '<<y<<endl;

		add(x,y);add(y,x);

	}

	get(Q);dfs(1);dfs(1,1);

	build(1,1,n);

	rep(1,n,i)f[i]=fa[i];

	rep(1,Q,i)

	{

		char ch=getc();

		while(ch!='q'&&ch!='O')ch=getc();

		int get(x)+1;

		if(ch=='O')access(x);

		else asksum(x);

	}

	return 0;

}

3.28 省选模拟赛 染色 LCT+线段树的相关教程结束。