借用学长的活：60种颜色是突破口（我咋不知道QAQ）

好像这几道都是线段树+dfs序？？于是你可以把60种颜色压进一个long long 里，然后向上合并的时候与一下（太妙了~）

所以记得开long long (又调了一个半小时。。。打代码只花了20分钟？？？)

#include
     
      #include
      
       #define ll long long#define R register int#define ls (tr<<1)#define rs (tr<<1|1)const int N=400010;using namespace std;inline ll g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;}int n,m,cnt,num;int vr[N<<1],nxt[N<<1],fir[N],dfn[N],sz[N],rw[N],w[N];ll sum[N<<2]; bool tg[N<<2];inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}inline ll lbt(ll x) {
    return x&-x;}inline int ppc(ll x) {R ret=0; while(x) x-=lbt(x),++ret; return ret;}void dfs(int u) { sz[u]=1,dfn[u]=++num,rw[num]=u;    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];        if(dfn[v]) continue;        dfs(v); sz[u]+=sz[v];    }}inline void build(int tr,int l,int r) {    if(l==r) {sum[tr]=1ll<
       
        >1;    build(ls,l,md),build(rs,md+1,r); sum[tr]=sum[ls]|sum[rs];}inline void spread(int tr) {    if(tg[tr]) tg[tr]=false,sum[ls]=sum[rs]=sum[tr],tg[ls]=tg[rs]=true;}inline void update(int tr,int l,int r,int LL,int RR,int inc) {    if(LL<=l&&r<=RR) {sum[tr]=1ll<
        
         >1; if(LL<=md) update(ls,l,md,LL,RR,inc); if(RR>md) update(rs,md+1,r,LL,RR,inc);    sum[tr]=sum[ls]|sum[rs];}inline ll query(int tr,int l,int r,int LL,int RR) {    if(LL<=l&&r<=RR) return sum[tr]; spread(tr); R md=(l+r)>>1,ret=0;    if(LL<=md) ret|=query(ls,l,md,LL,RR); if(RR>md) ret|=query(rs,md+1,r,LL,RR);    return ret;}signed main() {    n=g(),m=g(); for(R i=1;i<=n;++i) w[i]=g();    for(R i=2,u,v;i<=n;++i) u=g(),v=g(),add(u,v),add(v,u);    dfs(1); build(1,1,n);    for(R i=1;i<=m;++i) {        R k=g(),u=g(),inc;        if(k&1) inc=g(),update(1,1,n,dfn[u],dfn[u]+sz[u]-1,inc);        else printf("%d\n",ppc(query(1,1,n,dfn[u],dfn[u]+sz[u]-1)));    }} 
        
       
      
     

---

 

2019.04.19