Submission #892943

#	Time	Username	Problem	Language	Result	Execution time	Memory
892943		Alcabel	Power Plant (JOI20_power)	C++17	100 / 100	106 ms	29588 KiB

power

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

const int maxn = 2e5;
vector<int> g[maxn];
int dp[maxn][2];
string s;

int dfs(int v, int p) {
    int res = 0;
    for (const int& u : g[v]) {
        if (u != p) {
            res = max(res, dfs(u, v));
            dp[v][0] = max(dp[v][0], max(dp[u][1], max(dp[u][0] - 2 * (s[u] - '0'), (s[u] - '0'))));
            dp[v][1] += max(dp[u][1], max(dp[u][0] - 2 * (s[u] - '0'), (s[u] - '0')));
        }
    }
    dp[v][0] += (s[v] - '0');
    dp[v][1] -= (s[v] - '0');
    // cerr << "v: " << v << ", 0: " << dp[v][0] << ", 1: " << dp[v][1] << '\n';
    res = max(res, max(dp[v][0], dp[v][1]));
    return res;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].emplace_back(u);
        g[u].emplace_back(v);
    }
    cin >> s;
    cout << dfs(0, -1) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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