Submission #763015

#	Time	Username	Problem	Language	Result	Execution time	Memory
763015		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	166 ms	31968 KiB

power

#include <iostream>
#include <vector>
using namespace std;
vector<int> g[200005];
int a[200005], f[200005][5];
void dfs(int x, int p) {
    int c = 0, d = 0, ma = 0, ma2 = 0;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x);
        c += f[w][1];
        ma = max(ma, max(f[w][0], f[w][1]));
        ma2 = max(ma2, f[w][1]);
    }
    d = c;
    f[x][1] = max(a[x], c - a[x]);
    if (x == 1 && g[x].size() > 1) c -= a[x];
    else if (g[x].size() > 2) c -= a[x];
    c = max(c, ma);
    if (x == 1 && g[x].size() > 1) d -= a[x];
    else if (g[x].size() > 2) d -= a[x];
    ma2 += a[x];
    ma2 = max(ma2, d);
    f[x][0] = max(ma2, c);
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') a[i] = 1;
    }
    dfs(1, -1);
    cout << max(f[1][0], f[1][1]);
}

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