제출 #1064498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064498		aufan	Power Plant (JOI20_power)	C++17	100 / 100	95 ms	39252 KiB

power

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n;
        cin >> n;

        vector<vector<int>> v(n + 1);
        for (int i = 0; i < n - 1; i++) {
                int a, b;
                cin >> a >> b;

                v[a].push_back(b);
                v[b].push_back(a);
        }

        vector<int> ok(n + 1);
        for (int i = 1; i <= n; i++) {
                char c;
                cin >> c;

                ok[i] = (c == '1');
        }

        int ans = 0;
        vector<int> dp(n + 1);

        function<void(int, int)> dfs = [&](int x, int p) {
                dp[x] = ok[x];

                int cur = -ok[x];
                for (auto z : v[x]) {
                        if (z == p) continue;

                        dfs(z, x);

                        ans = max(ans, dp[z] + ok[x]);
                        cur += dp[z];
                }

                dp[x] = max(dp[x], cur);
                ans = max(ans, dp[x]);
        };

        dfs(1, 1);

        cout << ans << '\n';
        
        return 0;
}

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