Submission #1143231

#TimeUsernameProblemLanguageResultExecution timeMemory
1143231fryingducPower Plant (JOI20_power)C++20
100 / 100
66 ms27008 KiB
#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;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...