HE April Circuits 3B - Bear and Special Dfs ( Timestamp + Segment Tree + Modular Inverse )

https://www.hackerearth.com/april-circuits/algorithm/utkarsh-and-special-dfs/
Modifying some node u, changing a[ u ] to some new value x, the vis count of each node of subtree of u will be divided by the original a[ u ], and multiplied by x. We can make time stamp and transfer each node to some interval, then apply range multiplication and range sum query on segment tree. Since modulo participates in the calculation, it is not possible to simply divide any value. However, dividing some value x in a system of p-modulo, is equivalent to multiplying the inverse of x in p-modulo.
According to Euler's theorem:

and since phi( p ) = p - 1, when p is prime, where p = 1e9 + 7 in this problem,
we have little fermat's theorem x ^ ( p - 1 ) % p = 1, divide both sides by x, and we will have
x ^ ( p - 2 ) % p = x ^ ( -1 ) = inverse of x under p modulo

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int MAXQ = 1e5 + 5;
const int MAXX = 1e9 + 9;
const int MAXV = MAXN;

struct itvt{
    int sumv, mul_tag;
    int lb, rb;
    itvt *lc, *rc;
    itvt(): sumv( 0 ), mul_tag( 1 ), lc( NULL ), rc( NULL ){}
    void push(){
        lc->sumv = ( 1ULL * lc->sumv * mul_tag ) % MOD;
        rc->sumv = ( 1ULL * rc->sumv * mul_tag ) % MOD;
        lc->mul_tag = ( 1ULL * lc->mul_tag * mul_tag ) % MOD;
        rc->mul_tag = ( 1ULL * rc->mul_tag * mul_tag ) % MOD;
        mul_tag = 1;
    }
    void pull(){
        sumv = ( lc->sumv + rc->sumv ) % MOD;
    }
    void updateItvt( int ql, int qr, int v ){ // multiply interval by v
        if( qr < lb || rb < ql ) return;
        if( ql <= lb && rb <= qr ){
            sumv = 1ULL * sumv * v % MOD;
            mul_tag = 1ULL * mul_tag * v % MOD;
            return;
        }
        push();
        lc->updateItvt( ql, qr, v );
        rc->updateItvt( ql, qr, v );
        pull();
    }
    int qsum( int ql, int qr ){
        if( qr < lb || rb < ql ) return 0;
        if( ql <= lb && rb <= qr ){
            return sumv;
        }
        push();
        int res = 0;
        ( res += lc->qsum( ql, qr ) ) %= MOD;
        ( res += rc->qsum( ql, qr ) ) %= MOD;
        pull();
        return res;
    }
};

itvt* buildItvt( int lb, int rb ){
    itvt *t = new itvt();
    t->lb = lb, t->rb = rb;
    if( lb == rb ){
        t->sumv = 1;
        return t; // each leaf node is gonna be one
    }
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

int pw( int a, int p ){ // a ^ p
    int res = 1;
    while( p ){
        if( p & 1 )
            res = 1ULL * res * a % MOD;
        p >>= 1;
        a = 1ULL * a * a % MOD;
    }
    return res;
}

int inv( int v ){ // modular inverse of v
    return pw( v, MOD - 2 ); // little fermat's
}

int n, q;
int a[ MAXN ];
vector< int > G[ MAXN ];

int TIMESTAMP;
int in[ MAXN ], out[ MAXN ];

void dfs( int u ){
    in[ u ] = ++TIMESTAMP;
    for( int v : G[ u ] )
        if( !in[ v ] )
            dfs( v );
    out[ u ] = TIMESTAMP;
}

void initTimeStamp(){
    TIMESTAMP = 0;
    dfs( 1 );
}

int main(){
    scanf( "%d%d", &n, &q );
    for( int i = 0; i < n - 1; ++i ){
        int u, v; scanf( "%d%d", &u, &v );
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    initTimeStamp();
    itvt *root = buildItvt( 1, TIMESTAMP );
    for( int i = 1; i <= n; ++i ){
        int v; scanf( "%d", &v );
        root->updateItvt( in[ i ] + 1, out[ i ], a[ i ] = v );
    }
    for( int i = 0; i < q; ++i ){
        int op; scanf( "%d", &op );
        if( op == 1 ){
            int u, x; scanf( "%d%d", &u, &x );
            root->updateItvt( in[ u ] + 1, out[ u ], inv( a[ u ] ) );
            root->updateItvt( in[ u ] + 1, out[ u ], a[ u ] = x );
        } else{
            int u; scanf( "%d", &u );
            printf( "%d\n", root->qsum( in[ u ], out[ u ] ) );
        }
    }
    return 0;
}