Submission #766786

#	Time	Username	Problem	Language	Result	Execution time	Memory
766786		ParsaS	Power Plant (JOI20_power)	C++17	100 / 100	143 ms	27656 KiB

power

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5;
int n;
vector<int> adj[N];
string s;
int dp[N], up[N], par[N];

void dfs(int v, int p) {
    par[v] = p;
    int sum = 0;
    for (auto u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            sum += dp[u];
        }
    }
    dp[v] = max(0, sum - 1);
    if (s[v] == '0')
        dp[v] = sum;
    else
        dp[v] = max(dp[v], 1);
}
void dfs2(int v, int p) {
    int sum = 0;
    for (auto u : adj[v]) {
        if (u != p)
            sum += dp[u];
    }
    for (auto u : adj[v]) {
        if (u != p) {
            up[u] = max(0, up[v] + sum - dp[u] - 1);
            if (s[v] == '0')
                up[u] = up[v] + sum - dp[u];
            else
                up[u] = max(up[u], 1);
            dfs2(u, v);
        }
    } 
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int v, u; cin >> v >> u;
        v--, u--;
        adj[v].pb(u), adj[u].pb(v);
    }
    cin >> s;
    dfs(0, 0);
    dfs2(0, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            ans = max(ans, up[i] + 1);
            for (auto u : adj[i])
                if (u != par[i])
                    ans = max(ans, dp[u] + 1);
        }
    }
    cout << ans << '\n';
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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