제출 #1140049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140049		not_amir	Power Plant (JOI20_power)	C++20	100 / 100	75 ms	25376 KiB

power

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


int ans = 0;
int dfs(int v, int p, vector<vector<int>>& G, string& S) {
    int mans = 0 , sans = 0;
    for (int u : G[v]) {
        if (u == p)
            continue;
        int cans = dfs(u, v, G, S);
        mans = max(mans, cans);
        sans += cans;
    }
    int c = S[v - 1] == '1';
    sans = max(c, sans - c);
    ans = max({ans, sans, mans + c});
    return sans;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> G(n + 1);
    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;
    dfs(1, -1, G, S);
    cout << ans;
}

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