Submission #465496

#	Time	Username	Problem	Language	Result	Execution time	Memory
465496		MKutayBozkurt	Power Plant (JOI20_power)	C++17	100 / 100	206 ms	36420 KiB

power

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long

int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int x, y; cin >> x >> y, x--, y--;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    char x; cin >> x;
    a[i] = x - '0';
  }

  vector<int> dp(n);

  int ans = 0;

  function<void(int, int)> dfs = [&](int node, int parent) {
    dp[node] = -a[node];
    for (auto next : g[node]) {
      if (next == parent) continue;
      dfs(next, node);
      ans = max(ans, dp[next] + a[node]);
      dp[node] += dp[next];
    }
    dp[node] = max(dp[node], a[node]);
    ans = max(ans, dp[node]);
  };
  dfs(0, -1);
  cout << ans << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53