Submission #886642

#	Time	Username	Problem	Language	Result	Execution time	Memory
886642		stefanneagu	Power Plant (JOI20_power)	C++17	100 / 100	89 ms	25952 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5 + 1;

int v[nmax], dp[nmax], ans;
bool f[nmax];
vector<vector<int>> adj(nmax);

void dfs(int i, int tata) {
  for(auto fiu : adj[i]) {
    if(fiu != tata) {
      dfs(fiu, i);
    }
  }
  int sum = 0, maxx = 0;
  for(auto fiu : adj[i]) {
    sum += dp[fiu];
    maxx = max(maxx, dp[fiu]);
  }
  if(f[i]) {
    ans = max({ans, maxx + 1, sum - 1});
  } else {
    ans = max({ans, maxx, sum});
  }
  dp[i] = max(f[i] * 1, sum - f[i]);
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int n;
  cin >> n;
  adj.resize(n + 1);
  for(int i = 1; i < n; i ++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i = 1; i <= n; i ++) {
    char ch;
    cin >> ch;
    f[i] = ch - '0';
  }
  dfs(1, 0);
  cout << ans;
  return 0;
}

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