P3178 [HAOI2015]树上操作

#include<iostream>
using namespace std;
#define int long long
const int N = 100000 + 1 ;
int n , m , a [ N ] ;
struct node {
    int tag , sum;
};
node tree [ N << 2 ] ;
namespace xds {
    void build ( int k , int l , int r )
    {
        tree [ k ] . tag = - ( 1 << 30 ) ;
        if ( l == r ) {
            tree [ k ] . sum = a [ l ];
            return;
        }
        int mid = l + r >> 1 ;
        build ( k << 1 , l , mid ) ;
        build ( k << 1 | 1 , mid + 1 , r ) ;
        tree [ k ] . sum = tree [ k << 1 ] . sum + tree [ k << 1 | 1 ] . sum ;
        return;
    }
    void push_down ( int k , int l , int mid , int r )
    {
        if ( tree [ k ] . tag == - ( 1 << 30 ) )
            return;

        if ( tree [ k << 1 ] . tag != - ( 1 << 30 ) )
            tree [ k << 1 ] . tag += tree [ k ] . tag;
        else
            tree [ k << 1 ] . tag = tree [ k ] . tag;
        if ( tree [ k << 1 | 1 ] . tag != - ( 1 << 30 ) )
        tree [ k << 1 | 1 ] . tag += tree [ k ] . tag;
        else
            tree [ k << 1 | 1 ] . tag = tree [ k ] . tag;

        tree [ k << 1 ] . sum += ( mid - l + 1 ) * tree [ k ] . tag ;
        tree [ k << 1 | 1 ] . sum += ( r - mid ) * tree [ k ] . tag ;

        tree [ k ] . tag = - ( 1 << 30 ) ;
        return ;
    }
    void update ( int k , int l , int r , int x , int y , int z )
    {
        if ( l >= x && r <= y )
        {
            tree [ k ] . sum += ( r - l + 1 ) * z ;
            if ( tree [ k ] . tag != - ( 1 << 30 ) )
                tree [ k ] . tag += z;
            else
                tree [ k ] . tag = z;
            // cout << tree [ k ] . tag << endl;
            return;
        }
        int mid = l + r >> 1 ;
        push_down ( k , l , mid , r ) ;
        if ( x <= mid ) update( k << 1 , l , mid , x , y , z );
        if ( y > mid ) update ( k << 1 | 1 , mid + 1 , r , x , y , z );
        tree [ k ] . sum = tree [ k << 1 ] . sum + tree [ k << 1 | 1 ] . sum;
        return;
    }
    int query ( int k , int l , int r , int x , int y )
    {
        if ( l >= x && r <= y )
            return tree [ k ] . sum ;
        int mid = l + r >> 1 ;
        push_down ( k , l , mid , r ) ;
        int rhs = 0 ;
        if ( x <= mid ) rhs += query ( k << 1 , l , mid , x , y );
        if ( y > mid ) rhs += query ( k << 1 | 1 , mid + 1 , r , x , y );
        return rhs ;
    }
}int cnt , h [ N ] , to [ N * 2 ] , nt [ N * 2 ];
int value [ N ] , dep [ N ] , fa [ N ] , top [ N ] , mson [ N ] , siz [ N ] ;
int vt [ N ] , num ;
void merge ( int x , int y )
{
    nt [ ++ cnt ] = h [ x ] ;
    h [ x ] = cnt;
    to [ cnt ] = y;
    return ;
}
void dfs_1 ( int x , int father )
{
    dep [ x ] = dep [ father ] + 1;
    fa [ x ] = father;
    siz [ x ] = 1;
    int maxsize = -1;
    for ( int i = h [ x ] ; i ; i = nt [ i ] )
    {
        int y = to [ i ];
        if ( y == father ) continue;
        dfs_1 ( y , x );
        siz [ x ] += siz [ y ];
        if ( siz [ y ] > maxsize ) maxsize = siz [ y ] , mson [ x ] = y ;
    }
    return ;
}
void dfs_2 ( int x , int topfa )
{
    top [ x ] = topfa;
    vt [ x ] = ++ num;
    a [ num ] = value [ x ] ;
    if ( mson [ x ] ) dfs_2 ( mson [ x ] , topfa );
    for ( int i = h [ x ] ; i ; i = nt [ i ] )
    {
        int y = to [ i ];
        if ( y == fa [ x ] || y == mson [ x ] )
            continue;
        dfs_2 ( y , y ) ;
    }
    return ;
}
void cz_1 ( int x , int z )
{
    xds :: update ( 1 , 1 , n , vt [ x ] , vt [ x ] + siz [ x ] - 1 , z ) ;
}
int cz_2 ( int x )
{
    int ans = 0 ;
    while ( top [ x ] != 1 ) {
        ans += xds :: query ( 1 ,1 , n , vt [ top [ x ] ] , vt [ x ] ) ;
        // cout << top [ x ] << " " << x << endl;
        x = fa [ top [ x ] ] ;
    }
    ans += xds :: query ( 1 , 1 , n , 1 , vt [ x ] ) ;
    return ans ;
}
void cz_3 ( int x , int z )
{
    xds :: update ( 1 , 1 , n , vt [ x ] , vt [ x ] , z ) ;
}
signed main ( ) {
    // freopen ( "text.in" , "r" , stdin ) ;
    // freopen ( "text.out" , "w" , stdout ) ;
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; i ++ )
        cin >> value [ i ] ;
    for ( int i = 1 ; i < n ; i ++ ) {
        static int x , y;
        cin >> x >> y ;
        merge ( x , y ) , merge ( y , x ) ;
    }
    dfs_1 ( 1 , 0 ) ;
    dfs_2 ( 1 , 1 );
    xds :: build ( 1 , 1 , n ) ;
    for ( int i = 1 ; i <= m ; i ++ ) {
        static int op , x , a , y ;
        cin >> op;
        if ( op == 1 ) {
            cin >> x >> a;
            cz_3 ( x , a );
        }
        if ( op == 2 ) {
            cin >> x >> y;
            cz_1 ( x , y );
        }
        if ( op == 3 ) {
            cin >> x ;
            cout << cz_2 ( x ) << endl;
            // cout << "/-------------------分割线--------------------/" << endl;
        }
    }
    return 0 ;
}