CFR 533 B. Work Group ( DP )

Problem - B - Codeforces

題意：
給一棵以 1 為根的樹，以及點的權重。求一個集合，使得集合內每個點，以自身為子樹的根時，子樹內所有自身以外的點在集合中出現偶數次。問最大可能權重總和。

資料規模：
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 為根的子樹，子樹內選取的點數量為奇數時，最大可能權重和。
先考慮沒有 i 本身的情況隨便算，而有 i 的情況則只能來自沒有 i 而為偶數的情況。

時間 / 空間複雜度：
O( N )

注意：
第 23 行如果沒有，則在拜訪當前點的第一棵子樹時，會產生明明不能轉移自奇數總和，卻轉移的情況。

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