Submission #1274808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274808		SnowRaven52	Power Plant (JOI20_power)	C++20	100 / 100	76 ms	26964 KiB

power

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

int n;
vector<vector<int>> g;
string s;
long long ans = 0;
vector<long long> f;

void dfs(int u, int p) {
    for (int v : g[u]) if (v != p) dfs(v, u);
    long long mx = 0;
    for (int v : g[u]) if (v != p) { f[u] += f[v]; mx = max(mx, f[v]); }
    if (s[u] == '1') {
        ans = max(ans, mx + 1);
        f[u]--;
        ans = max(ans, f[u]);
        if (f[u] < 1) f[u] = 1;
    }
    ans = max(ans, f[u]);
}

int main() {
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    dfs(1, 0);
    cout << ans << endl;
}

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