Submission #1143231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143231		fryingduc	Power Plant (JOI20_power)	C++20	100 / 100	66 ms	27008 KiB

power

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, a[maxn];
int f[maxn], sum[maxn];
string s;
vector<int> g[maxn];
int res;

void dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    dfs(v, u);
    f[u] = max(f[u], f[u] + f[v]);
    res = max(res, f[v] + a[u]);
  }
  f[u] = max(f[u] - a[u], a[u]);
  res = max(res, f[u]);
  debug(u, a[u], f[u]);
}

void solve() {
  cin >> n;
  for(int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cin >> s;
  for(int i = 1; i <= n; ++i) {
    a[i] = (s[i - 1] - '0'); 
  }
  dfs(1, 0);
  
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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