New Year Tree

关于子树的修改和查询

很容易想到树链剖分

用序建立线段树

线段树中保存每个节点的颜色信息

由于颜色最多种所以可以压缩为二进制数

然后维护一个懒标记,就是裸题了

(另外,我是真不喜欢写树的题啊!!!!!)

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
typedef long long ll;
const int maxn = 8e5+10;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = (edge){v,head[u]},head[u]=cnt; }
int fa[maxn],deep[maxn],son[maxn],siz[maxn],w[maxn],n,m;
void dfs1(int u,int f,int depth)
{
    deep[u] = depth; siz[u] = 1; fa[u] = f;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==f )    continue;
        dfs1(v,u,depth+1);
        siz[u] += siz[v];
        if( siz[son[u]]<siz[v] )    son[u] = v;
    }
}
ll wn[maxn];
int id[maxn],kl,top[maxn];
void dfs2(int u,int ffa )
{
    id[u] = ++kl,wn[kl] = 1ll<<w[u],top[u] = ffa;
    if( son[u]==0 )    return;
    dfs2( son[u],ffa );
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==fa[u]||v==son[u] )    continue;
        dfs2(v,v);
    }
}
ll laz[maxn<<1],a[maxn<<1];
void pushup(int rt,int l,int r)    { a[rt] = a[ls]|a[rs]; }
void pushdown(int rt,int l,int r)
{
    if( laz[rt]==0 )    return;
    a[ls]=a[rs]=laz[ls]=laz[rs]=laz[rt];
    laz[rt]=0;
}
void build(int rt,int l,int r)
{
    if( l==r ){ a[rt]=wn[l]; return; }
    build( lson ); build( rson );
    pushup(rt,l,r);
}
void update(int rt,int l,int r,int L,int R,ll val)
{
    if( l>R||r<L )    return;
    if( l>=L&&r<=R ) { a[rt]=laz[rt]=val; return; }
    pushdown(rt,l,r);
    update(lson,L,R,val); update(rson,L,R,val);
    pushup(rt,l,r);
}
ll ask(int rt,int l,int r,int L,int R)
{
    if( l>R||r<L )    return 0;
    if( l>=L&&r<=R )    return a[rt];
    pushdown(rt,l,r);
    return ask(lson,L,R)|ask(rson,L,R);
}
int zhuan(ll x){ int ans = 0; while( x ){ ans += (x&1); x>>=1; } return ans; }
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%d",&w[i] );
    for(int i=1;i<n;i++)
    {
        int l,r; scanf("%d%d",&l,&r);
        add(l,r); add(r,l);
    }
    dfs1(1,0,1); dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int type,v,c; scanf("%d",&type);
        if( type==1 )
        {
            scanf("%d%d",&v,&c);
            update(1,1,n,id[v],id[v]+siz[v]-1,1ll<<c);
        }
        else
        {
            scanf("%d",&v);
            printf("%d\n",zhuan(ask(1,1,n,id[v],id[v]+siz[v]-1) ) );
        }
    }
}