Submission #763616

#	Time	Username	Problem	Language	Result	Execution time	Memory
763616		ind1v	Power Plant (JOI20_power)	C++11	100 / 100	118 ms	29624 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n;
vector<int> g[N];
string s;
int dp[N], ans[N];

void dfs(int u, int p) {
  dp[u] = -(s[u] - '0');
  int mx = 0;
  for (auto &v : g[u]) {
    if (v != p) {
      dfs(v, u);
      dp[u] += dp[v];
      ans[u] = max(ans[u], dp[v] + (s[u] - '0'));
    }
  }
  dp[u] = max(dp[u], (s[u] - '0'));
  ans[u] = max(ans[u], dp[u]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    cin >> a >> b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  cin >> s;
  s = '#' + s;
  dfs(1, 1);
  cout << *max_element(ans + 1, ans + n + 1);
  return 0;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:14:7: warning: unused variable 'mx' [-Wunused-variable]
   14 |   int mx = 0;
      |       ^~

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