DFS 序

noip · 2025-03-15 13:44:32 · 个人记录

#include <bits/stdc++.h>
#define MAXN 1000010

using namespace std;

int n , m , R , v[ MAXN ] , cnt; 
vector < int > edge[ MAXN ];

int l[ MAXN ] , r[ MAXN ];
//l[x]：DFS进入x点的时刻 
//r[x]：DFS走出x点的时刻 

void dfs( int x , int fa )
{
    l[x] = ++cnt;
    for( int i = 0 ; i < edge[x].size() ; i++ )
        if( edge[x][i] != fa )
            dfs( edge[x][i] , x );
    r[x] = cnt;
}

long long t[ MAXN ];

void modify( int x , int y )
{
    for( int i = x ; i <= n ; i += i & -i )
        t[i] += y;
}

long long find( int x )
{
    long long ans = 0;
    for( int i = x ; i ; i -= i & -i )
        ans += t[i];
    return ans;
}

int main()
{
    cin >> n >> m >> R;
    for( int i = 1 ; i <= n ; i++ )
        cin >> v[i];
    for( int i = 1 ; i < n ; i++ )
    {
        int x , y;
        cin >> x >> y;
        edge[x].push_back( y );
        edge[y].push_back( x );
    }
    dfs( R , 0 );
    for( int i = 1 ; i <= n ; i++ )
        modify( l[i] , v[i] );
    while( m-- )
    {
        int opt , a , x;
        cin >> opt >> a;
        if( opt == 1 )
        {
            cin >> x;
            modify( l[a] , x );
        }
        else
        {
            cout << find( r[a] ) - find( l[a] - 1 ) << endl;
        }
    }
    return 0;
}