Fshl0

ReRoot Technique DP

Jun 26th, 2020
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void ReRoot (int v, int p) {
  2.     res[v] = dp[v];
  3.     for (auto u: adj[v]) {
  4.         if (u == p) continue;
  5.         dp[v] -= max(dp[u], 0);
  6.         dp[u] += max(dp[v], 0);
  7.         ReRoot (u, v);
  8.         dp[u] -= max(dp[v], 0);
  9.         dp[v] += max(dp[u], 0);
  10.     }
  11.     return;
  12. }
RAW Paste Data