Submission #387549

#	Time	Username	Problem	Language	Result	Execution time	Memory
387549		timmyfeng	Power Plant (JOI20_power)	C++17	100 / 100	265 ms	28880 KiB

power

#include <bits/stdc++.h>
using namespace std;

const int N = 200001;

int profit[N], ans;
vector<int> adj[N];
string power;

void dfs_pull(int u, int p = 0) {
    profit[u] = '0' - power[u];
    for (auto c : adj[u]) {
        if (c != p) {
            dfs_pull(c, u);
            profit[u] += profit[c];
        }
    }
    profit[u] = max(profit[u], power[u] - '0');
}

void dfs_push(int u, int p = 0) {
    profit[u] = '0' - power[u];
    for (auto c : adj[u]) {
        profit[u] += profit[c];
    }

    ans = max(ans, profit[u]);

    for (auto c : adj[u]) {
        if (c != p) {
            int prv = profit[u];
            profit[u] = max(profit[u] - profit[c], power[u] - '0');
            dfs_push(c, u);
            profit[u] = prv;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    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 >> power;
    power = " " + power;

    ans = 1;
    for (int i = 1; i <= n; ++i) {
        for (auto j : adj[i]) {
            if (power[i] == '1' && power[j] == '1') {
                ans = 2;
            }
        }
    }

    dfs_pull(1);
    dfs_push(1);

    cout << ans << "\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53