2019.03.09 codeforces620E. New Year Tree（线段树+状态压缩）

传送门

题意：给一棵带颜色的树，可以给子树染色或者问子树里有几种不同的颜色，颜色值不超过606060。

思路：颜色值很小，因此状压一个区间里的颜色用线段树取并集即可。

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
typedef long long ll;
const int N=4e5+5;
vector<int>e[N];
int n,m,tot=0,in[N],out[N],pred[N],col[N];
ll bin[N];
void dfs(int p,int fa){
	pred[in[p]=++tot]=p;
	for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])^fa)dfs(v,p);
	out[p]=tot;
}
namespace SGT{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid (l+r>>1)
	ll sta[N<<2],cov[N<<2];
	inline void pushup(int p){sta[p]=sta[lc]|sta[rc];}
	inline void pushnow(int p,ll v){sta[p]=cov[p]=v;}
	inline void pushdown(int p){if(cov[p])pushnow(lc,cov[p]),pushnow(rc,cov[p]),cov[p]=0;}
	inline void build(int p,int l,int r){
		cov[p]=0;
		if(l==r){sta[p]=bin[col[pred[l]]];return;}
		build(lc,l,mid),build(rc,mid+1,r),pushup(p);
	}
	inline void update(int p,int l,int r,int ql,int qr,ll v){
		if(ql<=l&&r<=qr)return pushnow(p,v);
		pushdown(p);
		if(qr<=mid)update(lc,l,mid,ql,qr,v);
		else if(ql>mid)update(rc,mid+1,r,ql,qr,v);
		else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,mid+1,qr,v);
		pushup(p);
	}
	inline ll query(int p,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return sta[p];
		pushdown(p);
		if(qr<=mid)return query(lc,l,mid,ql,qr);
		if(ql>mid)return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,mid)|query(rc,mid+1,r,mid+1,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}
inline ll lowbit(const ll&x){return x&-x;}
inline int count_bit(ll x){
	int ret=0;
	while(x)x^=lowbit(x),++ret;
	return ret;
}
int main(){
	bin[0]=1;
	for(ri i=1;i<=60;++i)bin[i]=bin[i-1]<<1;
	n=read(),m=read();
	for(ri i=1;i<=n;++i)col[i]=read();
	for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
	dfs(1,0),SGT::build(1,1,n);
	for(ri op,v;m;--m){
		op=read();
		switch(op){
			case 1:v=read(),SGT::update(1,1,n,in[v],out[v],bin[read()]);break;
			case 2:v=read(),cout<<count_bit(SGT::query(1,1,n,in[v],out[v]))<<'\n';break;
		}
	}
	return 0;
}

巴特西

2019.03.09 codeforces620E. New Year Tree（线段树+状态压缩）

最新文章

热门文章