New Year Tree（dfs序+线段树+二进制）

题意： 给出一棵 n个节点的树，根节点为 1。每个节点上有一种颜色 ci。m次操作。操作有两种：
1 u c：将以 u为根的子树上的所有节点的颜色改为c。
2 u：询问以 u为根的子树上的所有节点的颜色数量。

题解：
一看题目好像是个dfs序+线段树的板子题，但是需要思考的是，怎么查询一段区间的颜色数目呢？
如果把这个问题解决了的话，这个题目也就相应的解决了。
看到颜色数目好像并不多，嗷，极好，60（2^60）正好在ll的范围内。
我们可以考虑每一位储存一种颜色，返回值为这段区间的(或)|。
这样子dfs序建线段树跑一边即可。

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=3e6+10;

vector<int> edge[maxn];

int tree[maxn],add[maxn];
int a[maxn],in[maxn],out[maxn],id[maxn];
int cnt;
void dfs(int u,int fa){
    in[u]=++cnt;
    id[cnt]=u;
    for(auto i:edge[u]){
        if(i==fa) continue;
        dfs(i,u);
    }
    out[u]=cnt;
}

void build(int node,int start,int ends){
    if(start==ends){
        tree[node]=1ll<<(a[id[start]]);
        //cout<<"tree: "<<a[id[start]]<<" "<<tree[node]<<endl;
        return ;
    }
    int mid=(start+ends)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,ends);
    tree[node]=tree[node*2]|tree[node*2+1];
}

void Add(int node,int val){
    //cout<<"val"<<val<<endl;
    add[node]=val;
    tree[node]=1ll<<val;
    //cout<<"addnode  "<<tree[node]<<endl;
    return ;
}
void push_down(int node){
    if(add[node]==0) return ;
    Add(node*2,add[node]);
    Add(node*2+1,add[node]);
    add[node]=0;
}
void update(int node,int start,int ends,int l,int r,int val){
    if(start>=l&&ends<=r) return Add(node,val);
    int mid=(start+ends)/2;
    push_down(node);
    if(l<=mid) update(node*2,start,mid,l,r,val);
    if(mid<r) update(node*2+1,mid+1,ends,l,r,val);
    tree[node]=tree[node*2]|tree[node*2+1];
}

int query(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r){
        //cout<<"tree[node]"<<l<<tree[node]<<endl;
        return tree[node];

    }
    int mid=(start+ends)/2;
    push_down(node);
    int ans=0;
    if(l<=mid) ans|=query(node*2,start,mid,l,r);
    if(mid<r) ans|=query(node*2+1,mid+1,ends,l,r);
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,-1);
    //cout<<"okok"<<endl;
    build(1,1,n);
    //cout<<"okok"<<endl;
    for(int i=0;i<m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            int x,y;
            cin>>x>>y;
            //cout<<in[x]<<" "<<out[x]<<endl;
            update(1,1,n,in[x],out[x],y);
        }
        else{
            int x;
            cin>>x;
            //cout<<"in:"<<in[x]<<"  out:"<<out[x]<<endl;
            int xxx=query(1,1,n,in[x],out[x]);
            int ans=0;
            //cout<<"xxx="<<xxx<<endl;
            for(int i=0;i<=60;i++){
                if(1&(xxx>>i)){
                    ans++;
                    //cout<<i<<" ";
                }
            }
            //cout<<endl;
            cout<<ans<<endl;
        }
    }
    return 0;

}