CFR Educational 6 E. New Year Tree ( Timestamp + Segment Tree + bits )

Problem - E - Codeforces
It's instinctive to come up with timestamp and segment tree. Initially I thought it would be fine with sets to maintain the set of colours, but now it seems like it wouldn't work. Maybe it's because my segment tree is pointer-based, which is notoriously slow. Do it with bits instead, since there are at most 60 colours, long long int will do.

template< class T1 >
int count_bit( T1 x ){
    return x == 0 ? 0 : ( x & ( T1 )1 ) + count_bit( x >> ( T1 )1 );
}

struct itvt{
    ll col, col_tag;
    int lb, rb;
    itvt *lc, *rc;
    itvt( int _lb, int _rb ): col( 0 ), col_tag( 0 ), lc( NULL ), rc( NULL ){
        lb = _lb, rb = _rb;
    }
    itvt* push(){
        if( col_tag )
            lc->col_tag = col_tag,
            lc->col = col_tag,
            rc->col_tag = col_tag,
            rc->col = col_tag,
            col_tag = 0;
        return this;
    }
    itvt* pull(){
        col = lc->col | rc->col;
        return this;
    }
    void update( int ql, int qr, int c ){
        if( qr < lb or rb < ql ) return;
        if( ql <= lb and rb <= qr ){
            col_tag = 1LL << c;
            col = col_tag;
            return;
        }
        push();
        lc->update( ql, qr, c );
        rc->update( ql, qr, c );
        pull();
    }
    ll query( int ql, int qr ){
        if( qr < lb or rb < ql ) return 0;
        if( ql <= lb and rb <= qr ) return col;
        push();
        ll col_bar = 0;
        col_bar |= lc->query( ql, qr );
        col_bar |= rc->query( ql, qr );
        pull();
        return col_bar;
    }
};

itvt* build_itvt( int lb, int rb ){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = build_itvt( lb, mid );
    t->rc = build_itvt( mid + 1, rb );
    return t->pull();
}

void dfs( int &tick, int u, int fa, vp &v_to_range, const vvi &G ){
    v_to_range[ u ].first = ++tick;
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        dfs( tick, v, u, v_to_range, G );
    }
    v_to_range[ u ].second = tick;
}

void solve(){
    int N, M; cin >> N >> M;
    vi C( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ], --C[ i ];

    vvi G( N );
    for( int i = 0; i < N - 1; ++i ){
        int u, v; cin >> u >> v;
        G[ u - 1 ].push_back( v - 1 );
        G[ v - 1 ].push_back( u - 1 );
    }

    vp v_to_range( N ); int dfs_tick = -1;
    dfs( dfs_tick, 0, -1, v_to_range, G );
    itvt *root = build_itvt( 0, N - 1 );
    for( int i = 0; i < v_to_range.size(); ++i )
        root->update( v_to_range[ i ].first, v_to_range[ i ].first, C[ i ] );

    for( int i = 0; i < M; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int u, c; cin >> u >> c; --u, --c;
            root->update( v_to_range[ u ].first, v_to_range[ u ].second, c );
        } else{
            int u; cin >> u; --u;
            cout << count_bit( root->query( v_to_range[ u ].first, v_to_range[ u ].second ) ) << "\n";
        }
    }
}