제출 #1324420

#제출 시각아이디문제언어결과실행 시간메모리
1324420sh_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);
        sum_children += dp[v];
    }

    if (s[u-1] == '1') {
        // Agar u tugunda generator bo'lsa:
        // 1. Faqat u tugunini yoqish yoki farzandlardan kelgan foydani olish: max(sum_children - 1, 1LL)
        // sum_children - 1 bo'lishiga sabab: u ni yoqsak, pastdagi bloklar bilan ulanishda 1 ta buzilish bo'lishi mumkin
        dp[u] = max(sum_children - 1, 1LL);
    } else {
        // Agar u tugunda generator bo'lmasa:
        dp[u] = sum_children;
    }
}

int main() {
    // Tezkor kiritish-chiqarish
    ios::sync_with_stdio(false);
    cin.tie(0);

    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 aylanamiz
    dfs(1, -1);

    // Yakuniy natija barcha tugunlar uchun hisoblangan maksimal qiymatdir
    // Chunki ildizda generator bo'lsa, sum_children o'zi ham yechim bo'lishi mumkin
    long long max_profit = 0;
    
    // Natijani hisoblashda ildizdagi holatni qayta tekshiramiz
    // DP mantiqiga ko'ra, ildiz uchun max_profitni sum_children orqali ham tekshirish kerak
    long long total_sum = 0;
    for (int v : adj[1]) {
        total_sum += dp[v];
    }
    
    // Agar ildizda generator bo'lsa, u yoqilganda foyda sum_children emas, sum_children + 1 bo'lishi ham mumkin
    // (Lekin bu holda qo'shni tugunlar buziladi)
    // To'g'ri natija:
    if (s[0] == '1') {
        max_profit = max(total_sum, dp[1] + 1);
    } else {
        max_profit = dp[1];
    }

    // Umumiy holatda barcha tugunlarni ildiz deb hisoblagandagi maksimalni olish:
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        long long current = 0;
        for (int v : adj[i]) {
            current += dp[v > i ? v : 0]; // Bu yerda mantiq biroz murakkabroq, 
        }
    }
    
    // Soddaroq yakuniy natija:
    cout << max(dp[1], (s[0] == '1' ? total_sum + 1 : 0)) << endl;

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