每日一题 CF620E New Year Tree 题解

首先我们把树上的子树问题转化成一维序列上的问题
之后我们发现颜色数的处理暴力合并比较慢，但是由于颜色数较小，我们可以直接压位一下，然后直接取个or就可以了
实际上不需要什么bitset，builtinpopcountll也是O(1)复杂度的！
具体实现线段树上打tag常规操作做一下。
代码：

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ------------------------------------------------ "<<endl
#define LL long long
#define DB double
#define mpt make_pair
#define pb push_back
inline LL read(){
    LL nm=0; bool fh=true; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return fh?nm:-nm;
}
#define M 400200
LL n,q,to[M<<1],nt[M<<1],fs[M],tot;
LL a[M],L[M],R[M],cnt,tg[M<<2],kd[M<<2];
inline void link(LL x,LL y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline void dfs(LL x,LL last=0){L[x]=++cnt; for(LL i=fs[x];i;i=nt[i]) if(to[i]^last) dfs(to[i],x); R[x]=cnt;}
inline void chg(LL x,LL vl){tg[x]=vl,kd[x]=(1ll<<vl);}
inline void pushdown(LL x){if(tg[x]){chg(x<<1,tg[x]),chg(x<<1|1,tg[x]),tg[x]=0;}}
inline void mdf(LL x,LL l,LL r,LL L,LL R,LL vl){
    if(L<=l&&r<=R){chg(x,vl);return;} LL mid=(l+r)>>1; pushdown(x);
    if(L<=mid) mdf(x<<1,l,mid,L,R,vl); if(R>mid) mdf(x<<1|1,mid+1,r,L,R,vl);
    kd[x]=kd[x<<1]|kd[x<<1|1];
}
inline LL qry(LL x,LL l,LL r,LL L,LL R){
    if(L<=l&&r<=R) return kd[x]; LL mid=(l+r)>>1,res=0ll; pushdown(x);
    if(L<=mid) res|=qry(x<<1,l,mid,L,R); if(R>mid) res|=qry(x<<1|1,mid+1,r,L,R);
    return res;
}

int main(){
    n=read(),q=read();
    for(LL i=1;i<=n;i++) a[i]=read();
    for(LL i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
    dfs(1); for(LL i=1;i<=n;i++) mdf(1,1,n,L[i],L[i],a[i]);
    while(q--){
        LL op=read(),x=read(),y;
        if(op==1) y=read(),mdf(1,1,n,L[x],R[x],y);
        else printf("%lld\n",(LL)__builtin_popcountll(qry(1,1,n,L[x],R[x])));
    }return 0;
}