Submission #1066368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066368		Minbaev	Power Plant (JOI20_power)	C++17	100 / 100	96 ms	39320 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';
        
}

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