Submission #1140049

#TimeUsernameProblemLanguageResultExecution timeMemory
1140049not_amirPower Plant (JOI20_power)C++20
100 / 100
75 ms25376 KiB
#include <bits/stdc++.h>
using namespace std;


int ans = 0;
int dfs(int v, int p, vector<vector<int>>& G, string& S) {
    int mans = 0 , sans = 0;
    for (int u : G[v]) {
        if (u == p)
            continue;
        int cans = dfs(u, v, G, S);
        mans = max(mans, cans);
        sans += cans;
    }
    int c = S[v - 1] == '1';
    sans = max(c, sans - c);
    ans = max({ans, sans, mans + c});
    return sans;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> G(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    string S;
    cin >> S;
    dfs(1, -1, G, S);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...