DFS 序

#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;
}