【每日一题】Accumulation Degree

Solution

普通的树形dp。

首先设为从点向的子树推流，所能达到的最大流量；

那么有：

其中为的孩子，为和之间的边的流量上限。

设为从向整棵树推流，所能达到的最大流量，那么有：

作两遍dfs，分别求出和的值，取输出即可，复杂度。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct edge {
  int v, cap;
};

vector<edge> G[200005];
ll dp[200005];

ll f(int v, int cap) {
  if ((int) G[v].size() == 1) {
    return cap;
  } else {
    return min<ll>(cap, dp[v]);
  }
}

void dfs(int u, int fa) {
  dp[u] = 0;
  for (auto e : G[u]) {
    if (e.v != fa) {
      dfs(e.v, u);
      dp[u] += f(e.v, e.cap);
    }
  }
}

void dfs(int u, int fa, int cap) {
  if (fa > 0) {
    dp[u] += min<ll>(cap, dp[fa] - f(u, cap));
  }
  for (auto e : G[u]) {
    if (e.v != fa) {
      dfs(e.v, u, e.cap);
    }
  }
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      G[x].push_back({ y, z });
      G[y].push_back({ x, z });
    }
    dfs(1, -1), dfs(1, -1, -1);
    ll res = *max_element(dp + 1, dp + 1 + n);
    cout << res << "\n";
  }
}