Submission #1295551

#TimeUsernameProblemLanguageResultExecution timeMemory
1295551baotoan655Power Plant (JOI20_power)C++20
100 / 100
92 ms26244 KiB
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 2e5 + 5;

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

int ans = 0;
int dp[N];

void dfs(int u, int p) {
    int mx = 0;
    int sum = 0;
    for (auto v : g[u]) if (v != p) {
            dfs(v, u);
            mx = max(mx, dp[v]);
            sum += dp[v];
        }
    mx += (s[u] - '0');
    sum -= (s[u] - '0');
    sum = max(sum, (s[u] - '0'));
    ans = max({ans, mx, sum});
    dp[u] = max(mx - 2 * (s[u] - '0'), sum);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

//    file("A") else file("task");
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    cin >> s;
    dfs(0, -1);
    cout << ans << '\n';
    return 0;
}

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