[BZOJ4817][SDOI2017]树点涂色：Link-Cut Tree+线段树

分析

与[BZOJ3779]重组病毒唯一的区别是多了一个链上求实链段数的操作。

因为每条实链的颜色必然不相同且一条实链上不会有两个深度相同的点（好像算法的正确性和第二个条件没什么关系，算了算了），画图分析可得，如果用\(dis[x]\)表示从\(x\)到根结点路径上的实链段数，则\(x\)到\(y\)路径上的实链段数可以表示为：

\[dis[x]+dis[y]-dis[lca(x,y)]*2+1
\]

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#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;

int ecnt,head[MAXN];

int fa[MAXN],dep[MAXN],siz[MAXN],pc[MAXN];

int top[MAXN],id[MAXN],num[MAXN],tot;

int maxn[MAXN<<2],atag[MAXN<<2],loc,ql,qr,kk;

int sta[MAXN],statop;

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	ecnt++;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

struct lct{

	int fa,ch[2];

	int tag;

}a[MAXN];

inline void subupd(int x,int kkk);

inline int 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;

	statop=1;

	sta[1]=y;

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

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

	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);

	}

}

#undef lc

#undef rc

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

	fa[x]=pre;

	a[x].fa=pre;

	dep[x]=depth;

	siz[x]=1;

	int maxsiz=-1;

	trav(i,x){

		int ver=e[i].to;

		if(ver==pre) continue;

		dfs1(ver,x,depth+1);

		siz[x]+=siz[ver];

		if(siz[ver]>maxsiz){

			maxsiz=siz[ver];

			pc[x]=ver;

		}

	}

}

void dfs2(int x,int topf){

	top[x]=topf;

	id[x]=++tot;

	num[tot]=x;

	if(!pc[x]) return;

	dfs2(pc[x],topf);

	trav(i,x){

		int ver=e[i].to;

		if(ver==fa[x]||ver==pc[x]) continue;

		dfs2(ver,ver);

	}

}

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

#define lc (o<<1)

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

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

	if(l==r){

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

		return;

	}

	build(lc,l,mid);

	build(rc,mid+1,r);

	maxn[o]=std::max(maxn[lc],maxn[rc]);

}

inline void segpushdown(int o){

	if(!atag[o]) return;

	maxn[lc]+=atag[o];

	maxn[rc]+=atag[o];

	atag[lc]+=atag[o];

	atag[rc]+=atag[o];

	atag[o]=0;

}

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

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

		maxn[o]+=kk;

		atag[o]+=kk;

		return;

	}

	segpushdown(o);

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

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

	maxn[o]=std::max(maxn[lc],maxn[rc]);

}

int squery(int o,int l,int r){

	if(l==r) return maxn[o];

	segpushdown(o);

	if(loc<=mid) return squery(lc,l,mid);

	else return squery(rc,mid+1,r);

}

int rquery(int o,int l,int r){

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

	segpushdown(o);

	int ret=0;

	if(mid>=ql) ret=std::max(ret,rquery(lc,l,mid));

	if(mid<qr) ret=std::max(ret,rquery(rc,mid+1,r));

	return ret;

}

#undef mid

#undef lc

#undef rc

inline int lca(int x,int y){

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

		x=fa[top[x]];

	}

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

}

inline void subupd(int x,int kkk){

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

	upd(1,1,n);

}

inline int subquery(int x){

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

	return rquery(1,1,n);

}

int main(){

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

	rin(i,2,n){

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

		add_edge(u,v);

		add_edge(v,u);

	}

	dfs1(1,0,1);

	dfs2(1,1);

	build(1,1,n);

	while(m--){

		int opt=read();

		if(opt==1){

			int x=read();

			access(x);

		}

		else if(opt==2){

			int ans=0;

			int x=read(),y=read();

			loc=id[x];ans+=squery(1,1,n);

			loc=id[y];ans+=squery(1,1,n);

			loc=id[lca(x,y)];ans-=(squery(1,1,n)<<1);

			ans++;

			printf("%d\n",ans);

		}

		else{

			int x=read();

			printf("%d\n",subquery(x));

		}

	}

	return 0;

}

巴特西

[BZOJ4817][SDOI2017]树点涂色：Link-Cut Tree+线段树

分析

代码

最新文章

热门文章