CFR 274 B. Zero Tree ( Tree DP )

Problem - B - Codeforces

題意：
有一棵樹，每個節點都有一個值。每次操作可以選一個含節點 1 的樹 ( 邊和節點連通的集合 )，將所有值加一或減一。求至少要多少次操作才能將所有值歸零。

資料規模：
節點數： 1 ≤ N ≤ 1e5
值域：abs( V[ i ] ) ≤ 1e9
時間限制：2000 ms
空間限制：256 MB

解法：
把節點一當根，轉為有根樹。考慮葉節點，修改次數很顯然。接著考慮它上面的節點，便會發現需要紀錄兩樣東西，加多少和減多少。另 dp_plus[ u ] 為 u 節點最少必須要被進行加的操作幾次，會發現為了讓 u 下面的節點都合法，dp_plus[ u ] = max{ dp_plus[ v ] | v is adjacent to u and v is deeper than u }，dp_minus[ u ] 同理。但為了要讓 u 本身合法，要算出 u 本身需要怎麼操作，這個用 dp_plus[ u ] - dp_minus[ u ] + V[ u ] 判斷一下就可以。

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

int N;
vvi G;
vi V;

void init(){
  cin >> N;
  G = vvi( N );
  for( int i = 0; i < N - 1; ++i ){
    int a, b; cin >> a >> b;
    G[ a - 1 ].emplace_back( b - 1 );
    G[ b - 1 ].emplace_back( a - 1 );
  }
  V = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> V[ i ];
  }
}

vl dp_plus, dp_minus;

void dfs( int u, int fa ){
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    dfs( v, u );
    upmax( dp_plus[ u ], dp_plus[ v ] );
    upmax( dp_minus[ u ], dp_minus[ v ] );
  }
  ll d = dp_plus[ u ] - dp_minus[ u ] + V[ u ];
  if( d > 0 ){
    dp_minus[ u ] += d;
  } else{
    dp_plus[ u ] -= d;
  }
}

void preprocess(){
  dp_plus = dp_minus = vl( N );
  dfs( 0, -1 );
}

void solve(){
  cout << dp_plus[ 0 ] + dp_minus[ 0 ] << endl;
}