Submission #1321009

#TimeUsernameProblemLanguageResultExecution timeMemory
1321009pobePower Plant (JOI20_power)C++20
6 / 100
1 ms568 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
class tree {
    int n;
    vector <int> dp;
    vector <vector <int>> gr;
    string is;
    int ans = 0;
    void dfs(int num, int last) {
        int counter = 0;
        for (int next : gr[num]) {
            if (next != last) {
                dfs(next, num);
                if (dp[next] > 0) {
                    ++counter;
                }
                dp[num] += dp[next];
            }
        }
        if (is[num] == '1') {
            if (counter < 2) {
                ans = max(ans, dp[num] + 1);
            }
            dp[num] = max(dp[num] - 1, 1LL);
        }
        ans = max(ans, dp[num]);
    }
public:
    void init() {
        cin >> n;
        dp.resize(n);
        gr.resize(n);
        for (int i = 0; i < n - 1; ++i) {
            int a, b;
            cin >> a >> b;
            --a;
            --b;
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        cin >> is;
    }
    void get_ans() {
        dfs(0, 0);
        cout << ans << '\n';
    }
};
void solve() {
    tree now;
    now.init();
    now.get_ans();
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...