CF620E New Year Tree (线段树+状压）

题目链接
题目大意：

树初始每个节点也有颜***r>总体思路：
题目是在每一棵子树整体做一个修改，所以我们就没有必要用树剖来写了。直接通过一边DFS来的到整棵树DFS序列，于是我们就将问题在一棵子树上进行操作转化为在一段连续的区间经行操作，这时候我们就可以用线段树来维护区间信息了。
我们可以注意到所有颜色的种类是有60种，所有我们可以用状态压缩来表示一棵树不同颜色的状态。每一中颜色存在为1，对应状态long long的一位。区间合并我们用|运算就可以了，注意每次更新是将前一次的颜色覆盖掉，所以lazy和sum表示也会直接被覆盖掉。
总之看见状态数比较小就可以考虑用状压来表示状态。
代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll x,y;
ll inx;
ll idx;
ll ch,c;
ll l,r;
ll a[400005];
ll h[400005],e[400005*2],ne[400005*2];
ll s[400005],dfsxu[400005],ni[400005];
struct ty{
    ll l,r;
    ll sum;
    ll lazy;
    ty():l(0),r(0),sum(0),lazy(0){ }
};
ty tr[400005*4];
void add(ll x,ll y){
    ne[inx]=h[x];e[inx]=y;h[x]=inx++;
    return ;
}
void dfs(ll u,ll fa){
    s[u]=++idx;
    dfsxu[idx]=u;
    for(ll i=h[u];i!=-1;i=ne[i]){
        int to=e[i];
        if(to==fa) continue;
        dfs(to,u);
    }
    ni[u]=idx;
    return ;
}
void pushup(ll u){
    tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;
    return ;
}
void build(ll u,ll l,ll r){
    tr[u].l=l; tr[u].r=r;
    if(l==r){
        tr[u].sum=1ll<<a[dfsxu[l]];
        tr[u].lazy=0;
        return ;
    }
    ll mind=(l+r)>>1;
    build(u<<1,l,mind);
    build(u<<1|1,mind+1,r);
    pushup(u);
    return ;
}
void pushdown(ll u){
    if(tr[u].lazy){
        tr[u<<1].sum=tr[u].lazy;
//如果每一更新不会覆盖掉上一次的状态，那tr[u<<1].sum|=tr[u].lazy;lazy标记同理
        tr[u<<1|1].sum=tr[u].lazy;
        tr[u<<1].lazy=tr[u].lazy;
        tr[u<<1|1].lazy=tr[u].lazy;
        tr[u].lazy=0;
    }
    return ;
}
void modify(ll u,ll l,ll r,ll da){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum=1ll<<da;
        tr[u].lazy=1ll<<da;
        return ;
    }
    pushdown(u);
    ll mind=(tr[u].l+tr[u].r)>>1;
    if(l<=mind) modify(u<<1,l,r,da);
    if(r>mind) modify(u<<1|1,l,r,da);
    pushup(u);
    return ;
}
ll query(ll u,ll l,ll r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum;
    }
    pushdown(u);
    ll ans=0;
    ll mind=(tr[u].l+tr[u].r)>>1;
    if(l<=mind) ans|=query(u<<1,l,r);
    if(r>mind) ans|=query(u<<1|1,l,r);
    return ans;
}
ll lowbit(ll i){
    return i&-i;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf(" %lld %lld",&n,&m);
    for(ll i=1;i<=n;i++) scanf(" %lld",&a[i]);
    for(ll i=1;i<n;i++){
        scanf(" %lld %lld",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,-1);
    build(1,1,n);
    for(ll i=1;i<=m;i++){
        scanf(" %lld",&ch);
        if(ch==1){
            scanf(" %d %d",&x,&c);
            l=s[x]; r=ni[x];
            modify(1,l,r,c);
        }
        else{
            scanf(" %d",&x);
            l=s[x]; r=ni[x];
            ll temp=query(1,l,r);
            ll cnt=0;
            while(temp>0){
                cnt++;
                temp-=lowbit(temp);
            }
            printf("%lld\n",cnt);
        }
    }
    return 0;
}