제출 #702345

#제출 시각아이디문제언어결과실행 시간메모리
702345leeh18Power Plant (JOI20_power)C++17
47 / 100
1586 ms14152 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (auto i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<bool> s(n);
    auto ans = 0;
    for (auto i = 0; i < n; ++i) {
        char c;
        cin >> c;
        s[i] = (c == '1');
        ans += int(s[i]);
    }
    ans = min(ans, 2);
    auto f = [&](auto self, int u, int p) -> int {
        auto sum = 0;
        for (auto v : adj[u]) {
            if (v != p) {
                sum += self(self, v, u);
            }
        }
        return (s[u] ? max(sum - 1, 1) : sum);
    };
    for (auto i = 0; i < n; ++i) {
        ans = max(ans, f(f, i, i));
    }
    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...