2017-04-11

【bzoj4817】树点涂色

本文为博主原创，未经许可不得转载

AC通道

做完这道题我才知道LCT还可以这样用：用虚边和实边统计答案

刚开始时所有的边都是虚边，答案就是路径上的虚边数量

操作一就是LCT中的access操作

操作二求一下lca减一下就好了

操作三搞一个dfs序维护子树即可

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500010
using namespace std;
struct node{int y,next;}e[MAXN<<1];
int n,m,len,dfs_clock,Link[MAXN],deep[MAXN],size[MAXN],dfn[MAXN],pos[MAXN],f[MAXN],delta[MAXN<<2],tr[MAXN<<2],son[MAXN][2],anc[MAXN][25];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y){
	e[++len].next=Link[x];Link[x]=len;e[len].y=y;
	e[++len].next=Link[y];Link[y]=len;e[len].y=x;
}
void build(int p,int l,int r){
	if(l==r)  {tr[p]=deep[pos[l]]; return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);  build(p<<1|1,mid+1,r);
	tr[p]=max(tr[p<<1],tr[p<<1|1]);
}
void pushdown(int p){
	int temp=delta[p];
	tr[p<<1]+=temp;  tr[p<<1|1]+=temp;
	delta[p<<1]+=temp;  delta[p<<1|1]+=temp;
	delta[p]=0;
}
void updata(int p,int l,int r,int x,int y,int v){
	pushdown(p);
	if(x>r||y<l)  return;
	if(x<=l&&y>=r)  {tr[p]+=v; delta[p]+=v; return;}
	int mid=(l+r)>>1;
	updata(p<<1,l,mid,x,y,v);  updata(p<<1|1,mid+1,r,x,y,v);
	tr[p]=max(tr[p<<1],tr[p<<1|1]);
}
int query(int p,int l,int r,int x,int y){
	pushdown(p);
	if(x>r||y<l)  return 0;
	if(x<=l&&y>=r)  return tr[p];
	int mid=(l+r)>>1;
	return max(query(p<<1,l,mid,x,y),query(p<<1|1,mid+1,r,x,y));
}
int get(int x){return son[f[x]][1]==x;}
bool isroot(int x){return son[f[x]][0]!=x&&son[f[x]][1]!=x;}
void rotate(int x){
	int y=f[x],z=f[y],which=get(x);
	if(!isroot(y))  son[z][son[z][1]==y]=x;
	son[y][which]=son[x][which^1];  f[son[y][which]]=y;
	son[x][which^1]=y;  f[y]=x;  f[x]=z;
}
void splay(int x){
	for(int y=f[x];!isroot(x);rotate(x),y=f[x])
		if(!isroot(y))  rotate(get(x)==get(y)?y:x);
}
int find(int x){while(son[x][0])x=son[x][0];return x;}
void access(int x){
	for(int t(0);x;t=x,x=f[x]){
		splay(x); 
		int y=find(son[x][1]);  updata(1,1,n,dfn[y],dfn[y]+size[y]-1,1);
		y=find(t);  updata(1,1,n,dfn[y],dfn[y]+size[y]-1,-1);
		son[x][1]=t;
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y])  swap(x,y);
	for(int i=20;i>=0;--i)  if(deep[anc[x][i]]>=deep[y])  x=anc[x][i];
	if(x==y)  return x;
	for(int i=20;i>=0;--i)  if(anc[x][i]!=anc[y][i])  x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
void dfs(int x,int fa){
	anc[x][0]=f[x];  size[x]=1;  dfn[x]=++dfs_clock;  pos[dfs_clock]=x;
	for(int i=1;i<=20;++i)  anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
		f[e[i].y]=x;  deep[e[i].y]=deep[x]+1;  dfs(e[i].y,x);
		size[x]+=size[e[i].y];
	}
}
void init(){
	n=read();  m=read();  deep[1]=1;
	for(int i=1;i<n;++i){int x=read(),y=read();insert(x,y);}
	dfs(1,0);  build(1,1,n);
}
void solve(){
	for(int i=1;i<=m;++i){
		int opt=read();
		if(opt==1){int x=read();access(x);}
		else if(opt==2){
			int x=read(),y=read(),t=lca(x,y);
			int ans=query(1,1,n,dfn[x],dfn[x])+query(1,1,n,dfn[y],dfn[y])-2*query(1,1,n,dfn[t],dfn[t])+1;
			printf("%d\n",ans);
		}
		else{int x=read();printf("%d\n",query(1,1,n,dfn[x],dfn[x]+size[x]-1));}
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init();  solve();
	return 0;
}

本文标题:【bzoj4817】树点涂色

文章作者:chty

发布时间:2017年04月11日 - 19时55分

最后更新:2018年03月24日 - 18时49分

许可协议:本文为博主原创，未经许可不得转载。