[Educational Codeforces Round 6][Codeforces 620E]New Year Tree

    题意：给出一棵以1为根的树，每个节点有一个颜色，颜色数<=60。有两种操作，操作1为将一棵以v为根的子树中的所有节点颜色变为\(a_i\)，操作2为查询以v为根的子树中的所有节点有多少种不同颜色。

    题解：考虑到颜色最多只有60种，所以可以用一个long long按位来记录颜色是否出现。对整棵树做出DFS序，然后建线段树，然后就是区间查询区间修改就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=7e5+10;

struct Segment_Tree
{
	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)
	int tag[maxn<<1];
	long long v[maxn<<1];

	void Update(int o)
	{
		v[o]=v[ls]|v[rs];
	}

	void Mark_Same(int o,int tg)
	{
		v[o]=1ll<<(tg-1);
		tag[o]=tg;
	}
	
	void Push_Down(int o)
	{
		if (!tag[o]) return;
		Mark_Same(ls,tag[o]);
		Mark_Same(rs,tag[o]);
		tag[o]=0;
	}

	void Change(int o,int l,int r,int a,int b,int tg)
	{
		if (a<=l && r<=b)
		{
			Mark_Same(o,tg);
			return;
		}
		Push_Down(o);
		if (a<=mid) Change(ls,l,mid,a,b,tg);
		if (b> mid) Change(rs,mid+1,r,a,b,tg);
		Update(o);
	}

	long long Query(int o,int l,int r,int a,int b)
	{
		if (a<=l && r<=b)
			return v[o];
		Push_Down(o);
		long long res=0;
		if (a<=mid) res|=Query(ls,l,mid,a,b);
		if (b> mid) res|=Query(rs,mid+1,r,a,b);
		Update(o);
		return res;
	}

	void Build(int o,int l,int r,int *cor)
	{
		if (l==r)
		{
			v[o]=1ll<<(cor[l]-1);
			return;
		}
		Build(ls,l,mid,cor);
		Build(rs,mid+1,r,cor);
		Update(o);
	}
}T;

int head[maxn],nxt[maxn<<1],E[maxn<<1],Ecnt;
int dfsq[maxn],tmp[maxn];
int l[maxn],r[maxn],Index;
int cor[maxn];
int n,m;

void Add_Edge(int x,int y) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

void DFS(int x,int father=0)
{
	l[x]=++Index;
	dfsq[Index]=x;
	for (int i=head[x];i;i=nxt[i]) if (E[i]!=father)
		DFS(E[i],x);
	r[x]=Index;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&cor[i]);
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add_Edge(x,y);
	DFS(1);
	for (int i=1;i<=n;i++) tmp[i]=cor[dfsq[i]];
	T.Build(1,1,n,tmp);
	while (m--)
	{
		int t,v,c;
		scanf("%d",&t);
		if (t==1)
		{
			scanf("%d%d",&v,&c);
			T.Change(1,1,n,l[v],r[v],c);
		}
		else
		{
			scanf("%d",&v);
			long long res=T.Query(1,1,n,l[v],r[v]);
			int ans=0;
			while (res)
			{
				ans+=res%2;
				res>>=1;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}