leetcode-go/poj/3585.accumulation-degree/main.cc

#include <cstdio>
#include <cstring>
#include <vector>

// For g++ only
#define FOREACH(i, a) for (__typeof(a.end()) i = a.begin(); i != a.end(); ++i)

using namespace std;

const int N = 200000;

// dp[i] means the max flow form node i to its subtree in [bottom-up dfs],
// if sub(i) means the sub nodes of node i, cap(i, j) means the cap of
// edge i -> j, deg(i) means the degree of node i, then we have:
// for j in sub(i),
// dp[i] = dp[i] + cap(i, j), if deg(j) == 1
//       = dp[i] + min(cap(i, j), dp[j]), if deg(j) > 1
// (init state: dp[i] = 0)
// In [top-down dfs], we have:
// for j in sub(i),
// dp[j] = dp[j] + cap(i, j), if deg(i) == 1
//       = dp[j] + min(cap(i, j) , dp[i] - min(cap(i, j), dp[j])), if deg(i) > 1
// init state: dp[root] = dp[root]
int dp[N + 1];

vector<pair<int, int> > adj[N + 1];

void bottom_up(int u, int p) {
  FOREACH(e, adj[u]) {
    int v = e->first;
    if (v == p) continue;
    bottom_up(v, u);
    if (adj[v].size() == 1)
      dp[u] += e->second;
    else
      dp[u] += min(dp[v], e->second);
  }
}

void top_down(int u, int p) {
  int deg = adj[u].size();
  FOREACH(e, adj[u]) {
    int v = e->first;
    if (v == p) continue;
    if (deg == 1)
      dp[v] += e->second;
    else
      dp[v] += min(e->second, dp[u] - min(e->second, dp[v]));
    top_down(v, u);
  }
}

int main() {
  int t, n, u, v, w;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) adj[i].clear();
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n - 1; i++) {
      scanf("%d %d %d", &u, &v, &w);
      adj[u].push_back(make_pair(v, w));
      adj[v].push_back(make_pair(u, w));
    }
    bottom_up(1, 0);
    top_down(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
  }
  return 0;
}