[BZOJ3779]重组病毒：Link-Cut Tree+线段树

分析

其实其他的题解说的都很清楚了。

一个点出发感染到根结点所花费的时间是路径上虚边的条数+1。

RELEASE相当于\(access()\)。

RECENTER相当于\(makeroot()\)。（虽然换根和打通路径的先后顺序不同但仔细想想本质其实是一样的）

所以我们可以通过维护一棵LCT来快速知道哪些结点与其父亲结点的连边由实变虚或由虚变实。

剩下的就是[BZOJ3083]遥远的国度了。

时间复杂度\(O(nlog^2n)\)。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <vector>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=100005;

int n,m,root;

std::vector<int> e[MAXN],ee[MAXN];

int fa[MAXN],dep[MAXN],siz[MAXN],id[MAXN],num[MAXN],tot;

int sta[MAXN],top;

int ql,qr;

LL sum[MAXN<<2],atag[MAXN<<2],kk;

char opt[10];

struct lct{

	int fa,ch[2];

	int tag;

}a[MAXN];

inline void add_edge(int bg,int ed){

	e[bg].push_back(ed);

}

void dfs(int x,int pre,int depth){

	fa[x]=pre;

	a[x].fa=pre;

	dep[x]=depth;

	id[x]=++tot;

	num[tot]=x;

	siz[x]=1;

	rin(i,0,(int)e[x].size()-1){

		int ver=e[x][i];

		if(ver==pre) continue;

		ee[x].push_back(ver);

		dfs(ver,x,depth+1);

		siz[x]+=siz[ver];

	}

}

inline void subupd(int x,LL kkk);

inline double subquery(int x);

#define lc a[x].ch[0]

#define rc a[x].ch[1]

inline bool isroot(int x){

	return a[a[x].fa].ch[0]!=x&&a[a[x].fa].ch[1]!=x;

}

inline void pushr(int x){

	std::swap(lc,rc);

	a[x].tag^=1;

}

inline void pushdown(int x){

	if(!a[x].tag) return;

	if(lc) pushr(lc);

	if(rc) pushr(rc);

	a[x].tag=0;

}

inline void rotate(int x){

	int y=a[x].fa,z=a[y].fa;

	int f=(a[y].ch[1]==x),g=a[x].ch[f^1];

	if(!isroot(y)) a[z].ch[a[z].ch[1]==y]=x;

	a[x].ch[f^1]=y;

	a[y].ch[f]=g;

	if(g) a[g].fa=y;

	a[y].fa=x;

	a[x].fa=z;

}

inline void splay(int x){

	int y=x,z=0;

	top=1;

	sta[1]=y;

	while(!isroot(y)) sta[++top]=y=a[y].fa;

	while(top) pushdown(sta[top--]);

	while(!isroot(x)){

		y=a[x].fa,z=a[y].fa;

		if(!isroot(y)){

			if((a[y].ch[0]==x)==(a[z].ch[0]==y)) rotate(y);

			else rotate(x);

		}

		rotate(x);

	}

}

inline int findroot(int x){

	while(pushdown(x),lc) x=lc;

	return x;

}

inline void access(int x){

	for(int y=0;x;x=a[y=x].fa){

		splay(x);

		if(rc){

			subupd(findroot(rc),1);

		}

		rc=y;

		if(rc){

			subupd(findroot(rc),-1);

		}

	}

}

inline void makeroot(int x){

	access(x);

	splay(x);

	pushr(x);

}

#undef lc

#undef rc

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc ((o<<1)|1)

inline void segpushdown(int o,int l,int r){

	if(!atag[o]) return;

	sum[lc]+=atag[o]*(mid-l+1);

	sum[rc]+=atag[o]*(r-mid);

	atag[lc]+=atag[o];

	atag[rc]+=atag[o];

	atag[o]=0;

}

void build(int o,int l,int r){

	if(l==r){

		sum[o]=dep[num[l]];

		return;

	}

	build(lc,l,mid);

	build(rc,mid+1,r);

	sum[o]=sum[lc]+sum[rc];

}

void upd(int o,int l,int r){

	if(ql>qr) return;

	if(ql<=l&&r<=qr){

		sum[o]+=kk*(r-l+1);

		atag[o]+=kk;

		return;

	}

	segpushdown(o,l,r);

	if(mid>=ql) upd(lc,l,mid);

	if(mid<qr) upd(rc,mid+1,r);

	sum[o]=sum[lc]+sum[rc];

}

LL query(int o,int l,int r){

	if(ql>qr) return 0;

	if(ql<=l&&r<=qr) return sum[o];

	segpushdown(o,l,r);

	LL ret=0;

	if(mid>=ql) ret+=query(lc,l,mid);

	if(mid<qr) ret+=query(rc,mid+1,r);

	return ret;

}

#undef mid

#undef lc

#undef rc

inline void subupd(int x,LL kkk){

	kk=kkk;

	if(id[root]<id[x]||id[root]>id[x]+siz[x]-1){

		ql=id[x],qr=id[x]+siz[x]-1;

		upd(1,1,n);

		return;

	}

	else if(root==x){

		ql=1,qr=n;

		upd(1,1,n);

		return;

	}

	else{

		int l=0,r=(int)ee[x].size()-1,ver=0;

		while(l<=r){

			int mid=((l+r)>>1),verr=ee[x][mid];

			if(id[verr]<=id[root]) ver=verr,l=mid+1;

			else r=mid-1;

		}

		ql=1,qr=id[ver]-1;

		upd(1,1,n);

		ql=id[ver]+siz[ver],qr=n;

		upd(1,1,n);

	}

}

inline double subquery(int x){

	if(id[root]<id[x]||id[root]>id[x]+siz[x]-1){

		ql=id[x],qr=id[x]+siz[x]-1;

		return (double)query(1,1,n)/siz[x];

	}

	else if(root==x){

		ql=1,qr=n;

		return (double)query(1,1,n)/n;

	}

	else{

		int l=0,r=(int)ee[x].size()-1,ver=0;

		LL ret=0;

		while(l<=r){

			int mid=((l+r)>>1),verr=ee[x][mid];

			if(id[verr]<=id[root]) ver=verr,l=mid+1;

			else r=mid-1;

		}

		ql=1,qr=id[ver]-1;

		ret+=query(1,1,n);

		ql=id[ver]+siz[ver],qr=n;

		ret+=query(1,1,n);

		return (double)ret/(n-siz[ver]);

	}

}

int main(){

	n=read(),m=read();

	rin(i,2,n){

		int u=read(),v=read();

		add_edge(u,v);

		add_edge(v,u);

	}

	root=1;

	dfs(1,0,1);

	build(1,1,n);

	while(m--){

		scanf("%s",opt+1);

		int x=read();

		if(opt[3]=='L'){

			access(x);

		}

		else if(opt[3]=='C'){

			makeroot(x);

			root=x;

		}

		else{

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

		}

	}

	return 0;

}

巴特西

[BZOJ3779]重组病毒：Link-Cut Tree+线段树

分析

代码

最新文章

热门文章