# CFR 533 B. Work Group ( DP )

Problem - B - Codeforces

The first line contains integer n (1 ≤ n ≤ 2e5) — the number of workers of the Big Software Company.
Then n lines follow, describing the company employees. The i-th line contains two integers pi, ai (1 ≤ ai ≤ 1e5) — the number of the person who is the i-th employee's immediate superior and i-th employee's efficiency. For the director p1 =  - 1, for all other people the condition 1 ≤ pi < i is fulfilled.
TL: 2000 ms
ML: 256 MB

dp[ i ][ j ]：以 i 為根的子樹，子樹內選取的點數量為奇數時，最大可能權重和。

O( N )

```int N;
vi P, A;

void init(){
cin >> N;
P = A = vi( N );
for( int i = 0; i < N; ++i ){
cin >> P[ i ] >> A[ i ];
if( P[ i ] != -1 ){
--P[ i ];
}
}
}

vvi G;
vvl dp;

void dfs( int u ){
if( G[ u ].empty() ){
dp[ u ][ 1 ] = A[ u ];
return;
}
dp[ u ][ 1 ] = - ( 1LL << 60 );
for( int v : G[ u ] ){
dfs( v );
ll c0 = dp[ u ][ 0 ], c1 = dp[ u ][ 1 ];
dp[ u ][ 0 ] = max( c0 + dp[ v ][ 0 ], c1 + dp[ v ][ 1 ] );
dp[ u ][ 1 ] = max( c0 + dp[ v ][ 1 ], c1 + dp[ v ][ 0 ] );
}
upmax( dp[ u ][ 1 ], dp[ u ][ 0 ] + A[ u ] );
}

void preprocess(){
G = vvi( N );
for( int i = 1; i < N; ++i ){
G[ P[ i ] ].emplace_back( i );
}
dp = vvl( N, vl( 2 ) );
dfs( 0 );
}

void solve(){
cout << max( dp[ 0 ][ 0 ], dp[ 0 ][ 1 ] ) << endl;
}
```