Submission #1274808

#TimeUsernameProblemLanguageResultExecution timeMemory
1274808SnowRaven52Power Plant (JOI20_power)C++20
100 / 100
76 ms26964 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> g;
string s;
long long ans = 0;
vector<long long> f;

void dfs(int u, int p) {
    for (int v : g[u]) if (v != p) dfs(v, u);
    long long mx = 0;
    for (int v : g[u]) if (v != p) { f[u] += f[v]; mx = max(mx, f[v]); }
    if (s[u] == '1') {
        ans = max(ans, mx + 1);
        f[u]--;
        ans = max(ans, f[u]);
        if (f[u] < 1) f[u] = 1;
    }
    ans = max(ans, f[u]);
}

int main() {
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> s;
    s = " " + s;
    f.assign(n + 1, 0);

    dfs(1, 0);
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...