[USACO19DEC]Bessie's Snow Cow

题目

显然这个子树操作是假的，我们dfs序一下就变成区间了

不难想到我们可以对于每一种颜色维护一个set，表示序列里哪些位置被涂上了这种颜色；对于修改操作，我们去对应颜色的set里处理一下和当前区间有交的区间，用线段树维护一下区间修改即可

至于复杂度，由于一段区间最多会被删除一次，所以是(O((n+q)log n))的

代码

include<bits/stdc++.h>
#define re register
#define LL long long
#define mp std::make_pair
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
typedef std::pair<int,int> pii;
struct E{int v,nxt;}e[maxn<<1];pii st[maxn];
int n,m,head[maxn],num,sum[maxn],dfn[maxn],top,__;
inline void add_(int x,int y){e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
struct Segment_Tree {
	int l[maxn<<2],r[maxn<<2],tag[maxn<<2];LL d[maxn<<2];
	inline void pushr(int i,int v) {d[i]+=1ll*v*(r[i]-l[i]+1);tag[i]+=v;}
	inline void pushdown(int i) {
		if(!tag[i])return;pushr(i<<1,tag[i]),pushr(i<<1|1,tag[i]);tag[i]=0;
	}
	inline void pushup(int i) {d[i]=d[i<<1]+d[i<<1|1];}
	void build(int x,int y,int i) {
		l[i]=x,r[i]=y;if(x==y)return;
		int mid=x+y>>1;build(x,mid,i<<1),build(mid+1,y,i<<1|1);
	}
	void add(int x,int y,int v,int i) {
		if(x<=l[i]&&y>=r[i]) {pushr(i,v);return;}
		int mid=l[i]+r[i]>>1;pushdown(i);
		if(x<=mid)add(x,y,v,i<<1);if(y>mid)add(x,y,v,i<<1|1);pushup(i);
	}
	LL query(int x,int y,int i) {
		if(x<=l[i]&&y>=r[i]) return d[i];
		int mid=l[i]+r[i]>>1;pushdown(i);
		return (x<=mid?query(x,y,i<<1):0)+(y>mid?query(x,y,i<<1|1):0);
	}
}T;
struct Set {
	std::set<pii> s;
	#define fl first
	#define fr second
	std::set<pii>::iterator it;
	inline void ins(int l,int r) {
		top=0;it=s.lower_bound(mp(l,0));
		if(it!=s.begin()) --it; 
		for(;it!=s.end();++it) {
			pii k=(*it);if(k.fr<l) continue;
			if(k.fl>r) break;
			st[++top]=k;T.add(k.fl,k.fr,-1,1);
		}
		if(!top) {
			s.insert(mp(l,r));T.add(l,r,1,1);return;
		}
		for(re int i=1;i<=top;i++) s.erase(st[i]);
		int L=l,R=r;if(st[1].fl<L) L=st[1].fl;if(st[top].fr>R) R=st[top].fr;
		s.insert(mp(L,R)),T.add(L,R,1,1);
	}
}seg[maxn];
void dfs(int x) {
	dfn[x]=++__;sum[x]=1;
	for(re int i=head[x];i;i=e[i].nxt)
		if(!dfn[e[i].v]) dfs(e[i].v),sum[x]+=sum[e[i].v];
}
int main() {
	n=read(),m=read();
	for(re int x,y,i=1;i<n;i++) x=read(),y=read(),add_(x,y),add_(y,x);
	dfs(1);T.build(1,n,1);int op,x,c;
	while(m--) {
		op=read(),x=read();
		if(op==1) c=read(),seg[c].ins(dfn[x],dfn[x]+sum[x]-1);
		if(op==2) printf("%lld
",T.query(dfn[x],dfn[x]+sum[x]-1,1));
	}return 0;
}