제출 #1324421

#제출 시각아이디문제언어결과실행 시간메모리
1324421sh_qaxxorov_571Power Plant (JOI20_power)C++20
0 / 100
2 ms332 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/**
 * JOI Open Contest 2020 - Power Plant
 * Murakkablik: O(N)
 */

const int MAXN = 200005;
vector<int> adj[MAXN];
long long dp[MAXN];
string s;

void dfs(int u, int p) {
    long long sum_children = 0;
    
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        // Faqat ijobiy foyda keltiradigan ostki daraxtlarni qo'shamiz
        if (dp[v] > 0) {
            sum_children += dp[v];
        }
    }

    if (s[u-1] == '1') {
        // Agar tugunda generator bo'lsa:
        // sum_children - 1: u ni yoqsak, pastdagi bloklar bilan ulanishda 1 ta ta'mir xarajatlari chiqadi [cite: 19, 64]
        // 1LL: Faqat shu tugunni yoqib, pastdagilarni o'chirish [cite: 17]
        dp[u] = max(sum_children - 1, 1LL);
    } else {
        // Agar generator bo'lmasa, shunchaki farzandlar foydasi [cite: 20]
        dp[u] = sum_children;
    }
}

int main() {
    // Kiritish va chiqarishni tezlashtirish
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

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

    cin >> s;

    // Daraxtni 1-tugundan boshlab hisoblaymiz 
    dfs(1, -1);

    // Ildiz tugunida maxsus holatni tekshiramiz:
    // Agar ildizda generator bo'lsa, uni yoqish orqali barcha farzandlardan 
    // kelgan ijobiy foydani buzilishsiz olish mumkin (sum_children + 1)
    long long root_sum = 0;
    for (int v : adj[1]) {
        if (dp[v] > 0) root_sum += dp[v];
    }

    long long ans = dp[1];
    if (s[0] == '1') {
        ans = max(ans, root_sum + 1);
    }

    cout << ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...