Submission #293428

#	Time	Username	Problem	Language	Result	Execution time	Memory
293428		rama_pang	Power Plant (JOI20_power)	C++14	100 / 100	220 ms	26196 KiB

power

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

const int MAXN = 200005;

int N;
string S;
vector<int> adj[MAXN];

int ans = 0;
int dp[MAXN];

void Dfs(int u, int p) {
  int max_subtree = 0;
  int sum_subtree = 0;
  for (auto v : adj[u]) if (v != p) {
    Dfs(v, u);
    max_subtree = max(max_subtree, dp[v]);
    sum_subtree += dp[v];
  }
  max_subtree += (S[u] - '0');
  sum_subtree -= (S[u] - '0');
  sum_subtree = max(sum_subtree, (S[u] - '0'));
  ans = max({ans, max_subtree, sum_subtree});
  dp[u] = max(max_subtree - 2 * (S[u] - '0'), sum_subtree);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  cin >> S;
  Dfs(0, -1);
  cout << ans << "\n";
  return 0;
}

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