CFR 383 C. Propagating tree ( TimeStamp + Segment Tree )

Problem - 383C - Codeforces
okuraofvegetableさんの記事を参考にしました ( 2015　木に対する一般的なテク達 )
www.npca.jp
行き戻りの配列がこう役に立つとは知りませんでした。勉強になりました。

#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;

struct itvt{
    int tag, sum;
    int lb, rb;
    itvt *lc, *rc;
    itvt(){ assert( false ); }
    itvt( int _l, int _r ): lb( _l ), rb( _r ), tag( 0 ), sum( 0 ), lc( NULL ), rc( NULL ){}
    void push(){
        lc->tag += tag;
        lc->sum += ( lc->rb - lc->lb + 1 ) * tag;
        rc->tag += tag;
        rc->sum += ( rc->rb - rc->lb + 1 ) * tag;
        tag = 0;
    }
    void pull(){
        sum += lc->sum + rc->sum;
    }
    void update( int ql, int qr, int val ){
        if( qr < lb || rb < ql ) return;
        if( ql <= lb && rb <= qr ){
            sum += ( rb - lb + 1 ) * val;
            tag += val;
            return;
        }
        push();
        int mid = lb + rb >> 1;
        if( ql <= mid ) lc->update( ql, qr, val );
        if( mid <  qr ) rc->update( ql, qr, val );
        pull();
    }
    int query( int k ){
        if( lb == rb ) return sum;
        push();
        int mid = lb + rb >> 1;
        int res;
        if( k <= mid ) res = lc->query( k );
        else res = rc->query( k );
        pull();
        return res;
    }
};

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

void buildTimeStamp( int u, int fa, const vector< vi > &G, vi &st, vi &ed, vi &tsarr ){
    st[ u ] = tsarr.size();
    tsarr.push_back( u );

    for( int v : G[ u ] ){
        if( v == fa ) continue;
        buildTimeStamp( v, u, G, st, ed, tsarr );
        tsarr.push_back( u );
    }

    ed[ u ] = tsarr.size() - 1;
}

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );

    int N, M; cin >> N >> M;

    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];

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

    vi st( N ), ed( N ), tsarr;
    buildTimeStamp( 0, -1, G, st, ed, tsarr );

    itvt *even, *odd;
    even = buildItvt( 0, tsarr.size() - 1 );
    odd = buildItvt( 0, tsarr.size() - 1 );
    for( int i = 0; i < M; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int x, val; cin >> x >> val;
            --x;
            if( st[ x ] & 1 ){
                odd->update( st[ x ], ed[ x ], val );
                even->update( st[ x ], ed[ x ], -val );
            } else{
                even->update( st[ x ], ed[ x ], val );
                odd->update( st[ x ], ed[ x ], -val );
            }
        } else{
            int x; cin >> x;
            --x;
            if( st[ x ] & 1 )
                cout << A[ x ] + odd->query( st[ x ] ) << "\n";
            else
                cout << A[ x ] + even->query( st[ x ] ) << "\n";
        }
    }

    return 0;
}