题意

给定一棵树，每个节点有一种颜色。我们需要支持两种操作：将某个子树中的所有节点染成同一种颜色，以及查询某个子树中不同颜色的数量。

思路

对树进行深度优先搜索（DFS），并按照访问顺序记录每个节点，得到 DFS 序（也称为欧拉遍历）。容易发现，任意节点的子树在 DFS 序中对应一个连续的区间。
由于颜色种类最多只有 $60$ 种，我们可以用 $64$ 位整数（C++ 中的 long long，Java 中的 long）的二进制位来存储颜色集合。
在 DFS 序上建立线段树，支持两种操作：

1. 将某个区间（子树）染成某种颜色；
2. 查询某个区间（子树）的颜色集合（以二进制掩码形式返回）。

算法步骤

1. 对树进行 DFS，记录每个节点的 DFS 序（进入时间戳和离开时间戳），从而确定每个子树对应的区间。
2. 用 $64$ 位整数表示颜色集合，每种颜色对应一个二进制位。
3. 在 DFS 序上建立线段树，每个节点存储该区间内所有颜色的二进制掩码。
4. 对于染色操作，将对应区间赋值为只包含目标颜色的掩码，并打上懒标记。
5. 对于查询操作，返回区间内所有颜色的掩码，然后统计其中 $1$ 的个数即为不同颜色的数量。

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 为节点数。
• 空间复杂度：$O(n)$。

代码说明

• 使用 DFS 预处理每个节点的子树区间。
• 线段树节点维护一个 long long 类型的掩码，表示当前区间内所有颜色的集合。
• 懒标记用于区间染色操作，标记值为目标颜色的掩码。
• 查询时合并左右子节点的掩码（按位或），最后统计结果掩码中 $1$ 的个数。

#include<bits/stdc++.h>
using namespace std;
#define sit set<node>::iterator

struct node{
	int l,r;
	mutable int v;
	node(int l,int r=0,int v=0):l(l),r(r),v(v){}
};

bool operator<(node x,node y){
	return x.l<y.l;
}

const int N=4e5+10;
int n,m,a[N],b[N],L[N],R[N],id[N],tim,vis[65];
set<node>s;

sit split(int x){
	sit it=s.lower_bound(node(x));
	if(it!=s.end()&&it->l==x)return it;
	--it;
	if(it->r<x)return s.end();
	int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert(node(l,x-1,v));
	return s.insert(node(x,r,v)).first;
}

void assign(int l,int r,int v){
	sit itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(node(l,r,v));
}

int query(int l,int r){
	sit itr=split(r+1),itl=split(l);
	memset(vis,0,sizeof(vis));
	int ret=0;
	for(sit it=itl;it!=itr;++it){
		if(!vis[it->v]){
			ret++;
			vis[it->v]=1;
			if(ret==60)return ret;
		}
	}
	return ret;
}

int fst[N],nxt[2*N],to[2*N],ecnt;

void adde(int u,int v){
	ecnt++;
	to[ecnt]=v;
	nxt[ecnt]=fst[u];
	fst[u]=ecnt;
}

void dfs(int u,int fa){
	L[u]=++tim;
	id[tim]=u;
	for(int i=fst[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs(v,u);
	}
	R[u]=tim;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		adde(u,v);adde(v,u);
	} 
	dfs(1,0);
	for(int i=1;i<=n;i++)b[L[i]]=a[i];
	for(int i=1,lst;i<=n+1;i++){
		if(b[i]!=b[i-1]){
			if(i>1)s.insert(node(lst,i-1,b[i-1]));
			lst=i;	
		}
	}
	for(int i=1,op,x,y;i<=m;i++){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d",&x,&y);
			assign(L[x],R[x],y);
		}else{
			scanf("%d",&x);
			printf("%d\n",query(L[x],R[x]));
		}
	}
	return 0;
}