CFR 232 C. On Changing Tree ( TimeStamp + Segment Tree )

Problem - C - Codeforces
CFR 383 C. Propagating tree ( TimeStamp + Segment Tree ) - 0w1
和這題十分相似。
注意到當操作為 u, x, k的時候，對於任一個 u的子樹的節點 v，其改變的量為 x - k * ( depth[ v ] - depth[ u ] )，其中 depth[ root ] = 0。拆解後發現是
( x + k * depth[ u ] ) - k * depth[ v ]，對於一個操作，前者和 v無關為定值，因此可以分開操作。

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

template< typename T >
T input(){
    T res;
    cin >> res;
    return res;
}

typedef vector< int > vi;

const int MOD = 1e9 + 7;

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->sum += 1LL * ( lc->rb - lc->lb + 1 ) * tag % MOD ) %= MOD;
        ( lc->tag += tag ) %= MOD;
        ( rc->sum += 1LL * ( rc->rb - rc->lb + 1 ) * tag % MOD ) %= MOD;
        ( rc->tag += tag ) %= MOD;
        tag = 0;
    }
    void pull(){
        ( sum = lc->sum + rc->sum ) %= MOD;
    }
    void update( int ql, int qr, int val ){
        if( qr < lb || rb < ql ) return;
        if( ql <= lb && rb <= qr ){
            ( sum += 1LL * ( rb - lb + 1 ) * val % MOD ) %= MOD;
            ( tag += val ) %= MOD;
            return;
        }
        push();
        int mid = lb + rb >> 1;
        if( lb <= mid ) lc->update( ql, qr, val );
        if( mid <  qr ) rc->update( ql, qr, val );
        pull();
    }
    int qsum( int ql, int qr ){
        if( qr < lb || rb < ql ) return 0;
        if( ql <= lb && rb <= qr ) return sum;
        push();
        int mid = lb + rb >> 1;
        int res = 0;
        if( ql <= mid ) ( res += lc->qsum( ql, qr ) ) %= MOD;
        if( mid <  qr ) ( res += rc->qsum( ql, qr ) ) %= MOD;
        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, int &cnt, int lv, const vector< vi > &G, vi &st, vi &ed, vi &dpt ){
    dpt[ u ] = lv;
    st[ u ] = ++cnt;
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        buildTimeStamp( v, u, cnt, lv + 1, G, st, ed, dpt );
    }
    ed[ u ] = cnt;
}

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

    int N; cin >> N;

    vector< vi > G( N );
    for( int i = 1; i < N; ++i )
        G[ input< int >() - 1 ].push_back( i );

    vi st( N ), ed( N ), depth( N );
    int _cnt;
    buildTimeStamp( 0, -1, _cnt = -1, 0, G, st, ed, depth );

    itvt *gain, *loss;
    gain = buildItvt( 0, N - 1 );
    loss = buildItvt( 0, N - 1 );
    int Q; cin >> Q;
    for( int i = 0; i < Q; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int v, x, k; cin >> v >> x >> k;
            --v;
            gain->update( st[ v ], ed[ v ], ( 1LL * k * depth[ v ] + x ) % MOD );
            loss->update( st[ v ], ed[ v ], k );
        } else{
            int v; cin >> v;
            --v;
            int ans = gain->qsum( st[ v ], st[ v ] ) -
                1LL * loss->qsum( st[ v ], st[ v ] ) * depth[ v ] % MOD;
            ans %= MOD; ans += MOD; ans %= MOD;
            cout << ans << "\n";
        }
    }

    return 0;
}