树剖求调
查看原帖
树剖求调
332123
LHLeisus楼主2022/9/20 18:10
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#define in inline
#define re register
#define FOR(i,a,b) for(re int i=a;i<=b;i++)
#define ROF(i,a,b) for(re int i=a;i>=b;i--)
#define pushup(u) tree[u]=tree[u<<1]+tree[u<<1|1]
using namespace std;
typedef long long ll;
const int N=6e5+5;
const int inf=114514;
//--------------SegMentTree
struct EE{
	int to,w,nex;
}edge[N<<1];
int head[N],cnt=0,tot=0;
void add(int u,int v,int w)
{
	edge[++cnt].nex=head[u];
	edge[cnt].to=v;
	edge[cnt].w=w;
	head[u]=cnt;
}
int dfn[N],pos[N],sz[N],a[N],dep[N],fa[N],top[N];
int max_son=-1,son[N];
struct E{
	int l,r,w,odt;
	E operator +(E const &x)const{
		return (E){l,x.r,0,inf};
	} 
}tree[N<<2];
void build(int u,int l,int r)
{
	if(l==r) 
	{
		tree[u]=(E){l,l,pos[l],inf};
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void pushdown(int u)
{
	E &y=tree[u];
	if(y.odt==inf) return ;
	E &ls=tree[u<<1];
	E &rs=tree[u<<1|1];
	int &k=y.odt;
	ls.odt=k;
	ls.w=k;
	rs.odt=k;
	rs.w=k;
	k=inf;
}
void modify(int u,int l,int r,int k)
{
	E &y=tree[u];
	if(y.l>=l&&y.r<=r)
	{
		y.odt=k;
		y.w=k;
		return ;
	}
	pushdown(u);
	if(y.l>r||y.r<l) return ;
	else{
		modify(u<<1,l,r,k);
		modify(u<<1|1,l,r,k);
	}
}
int query(int u,int k)
{
	E y=tree[u];
	pushdown(u);
	if(y.l==y.r&&y.l==k)
		return y.w;
	int mid=y.l+y.r>>1;
	if(k<=mid) return query(u<<1,k);
	else return query(u<<1|1,k);
}
//------------
void dfs_1(int u,int f)
{
	sz[u]=1;
	max_son=-1;
	dep[u]=dep[f]+1;
	fa[u]=f;
	for(int i=head[u];i;i=edge[i].nex)
	{
		int y=edge[i].to;
		if(y==f) continue;
		dfs_1(y,u);
		sz[u]+=sz[y];
		if(sz[y]>max_son)
		{
			son[u]=y;
			max_son=sz[y];
		}
	}
}
void dfs_2(int u,int topx)
{
	
	dfn[u]=++tot;
	pos[tot]=0;
	top[u]=topx;
	if(!son[u]) return ;
	dfs_2(son[u],topx);
	for(int i=head[u];i;i=edge[i].nex)
	{
		int y=edge[i].to;
		if(y==fa[u]||y==son[u]) continue;
		dfs_2(y,y);
	}
}
//----------------------------------
void modify_1(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		modify(1,dfn[top[x]],dfn[x],k);
		x=fa[top[x]];
	} 
	if(dep[x]>dep[y]) swap(x,y);
	modify(1,dfn[x],dfn[y],k);
}
int n,m,k;
int main()
{
	scanf("%d",&n);
	FOR(i,1,n-1)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,0);
		add(v,u,0);
	}
	scanf("%d",&m);
	dfs_1(1,1);
	dfs_2(1,1);
	build(1,1,n);
	while(m--)
	{
		int opt,u;
		scanf("%d%d",&opt,&u);
		if(opt==1)
		{
			modify(1,dfn[u],dfn[u]+sz[u]-1,1);
		}
		else if(opt==2)
		{
			modify_1(1,u,0);
		}
		else printf("%d\n",query(1,u));
	}
	return 0;
}
2022/9/20 18:10
加载中...