• 给定一个树，树上有颜色，将某一子树的颜色统一修改，求子树中颜色的数量

• 子树修改，子树求和，dfs序的知识（类似区间修改区间求和）

• 考虑到颜色的个数问题，利用位运算进行表示。

• 最后答案用二进制表示，\(\ 1\)表示有该种颜色，\(\ 0\)表示没有，

• 因此还需考虑答案\(\ 1\)的数量。

• dfs序问题自然用到线段树进行维护。

• 方案总数不是两个节点维护的方案数的简单相加，而是“|”（或）

• 答案维护的是颜色的个数，但不是具体数值

• 关于答案\(\ 1\)的个数,可以利用快速幂

• 也可利用\(\ lowbit\),作用是得到最后\(\ 1\)的位置上表示的数。

• 建树的时候特别记住需要\(\ long \ long\)的地方

  更加详细的内容

---

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int manx=1e6+10;
const int mamx = 1e7 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
struct nodee{
    int l,r;
    ll sum;
    ll add;
}e[manx<<2+2];
int clr[manx<<1];
struct node{
    int u;
    int v;
    int nxt;
    int w;
}ee[manx];
int head[manx],js,l[manx],r[manx],cnt,n,m,dfn[manx];
int add(int u,int v){
    ee[++cnt].u = u;
    ee[cnt].nxt = head[u];
    ee[cnt].v = v;
    //e[cnt].w = w;
    head[u] = cnt;
}
inline void init(){
    cnt=js=0;
    clr(head,-1);
}
//大法师
void dfs(int u, int pre){
    js++;
    l[u] = js;
    dfn[js] = u;
    for(int i = head[u];~i;i = ee[i].nxt){
        int v = ee[i].v;
        if( v == pre ) continue;
        dfs(v,u);
    }
    r[u] = js; //我们可以只记录他的入段，尾端那个不必重复
    return ;
}
//线段树
void uploat(int s){//上传
    e[s].sum = 0;
    if(e[s<<1].l) e[s].sum |=e[s<<1].sum ;
    if(e[s<<1|1].l ) e[s].sum |=e[s<<1|1].sum ;
}
void downloat(int i){
    if(e[i].add !=0){
        ll s = e[i].add ;//不要用int 用ll，作者就在这卡了一天
        e[i<<1].sum = s;
        e[i<<1].add = s;
        e[i<<1|1].add = s;
        e[i<<1|1].sum = s;
     e[i].add = 0;
    }
}
void build_up (int rt,int l,int r){
    e[rt].l = l;e[rt].r = r;
    if(l == r){
        e[rt].sum = (ll)1<<(clr[dfn[l]]);
        e[rt].add = 0;
        return;
    }
    int mid = (l+r) >> 1;
    build_up(rt<<1,l,mid);
    build_up(rt<<1|1,mid+1,r);
    e[rt].sum = e[rt<<1].sum | e[rt<<1|1].sum;
}
void updata(int i,int l,int r,int add){
    if(e[i].l >= l && e[i].r <= r)
    {
        e[i].sum = (ll)1<<add;
        e[i].add = (ll)1<<add;
        return;
    }
    int mid = (e[i].l  + e[i].r ) >> 1;
    downloat(i);
    if(mid >= r)updata(i<<1,l,r,add);
    else if(mid <l)updata(i<<1|1,l,r,add);
    else updata(i<<1,l,mid,add),updata(i<<1|1,mid+1,r,add);
    uploat(i);
 }
ll query(int i,int l,int r)
{
   if(e[i].l >= l && e[i].r <= r){
          return e[i].sum ;
   }
   downloat(i);
   int mid = (e[i].l +e[i].r ) >> 1;
    if(mid >= r)
        return  query(i<<1,l,r);
    else
        if(mid<l)
        return  query(i<<1|1,l,r);//熟悉的操作
        return  query(i<<1,l,mid)|query(i<<1|1,mid+1,r);
}
ll lowbit(ll x){
    return x&-x;//lowbit函数
}
int  ans;
int main(){
    n = read();
    m = read();
    init ();
    for(int i = 1;i <= n;i ++)
        clr[i] = read();
    for(int i = 1;i <= n - 1;i ++)
    {
        int x = read(),y = read();
        add(x,y);add(y,x);
    }
    dfs(1,0);
    build_up(1,1,n);//建树
    for(int i = 1;i <= m; i++)
    {
        int x = read();
        int y;
        int z;
        if(x == 1){
            y = read();z = read();
          updata(1,l[y],r[y],z);
        }
        else{
            ans = 0;y = read();
            ll diet = query(1,l[y],r[y]);
            while(diet>0){
                diet-=lowbit(diet);
                ans++;//判断1的个数
            }
            cout<<ans<<endl;//华丽收场
        }
    }
    return 0;
}