Submission #502471

#	Time	Username	Problem	Language	Result	Execution time	Memory
502471		tengiz05	Power Plant (JOI20_power)	C++17	100 / 100	195 ms	33100 KiB

power

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 200000;
int n;
std::vector<int> e[N];
int a[N], dp[N], sum[N];
void dfs(int u, int p) {
    for (int v : e[u]) {
        if (v != p) {
            dfs(v, u);
            sum[u] += dp[v];
        }
    }
    dp[u] = std::max(a[u], sum[u] - a[u]); 
}
int ans = 0;
void dfs2(int u, int p) {
    ans = std::max(ans, dp[u]);
    for (int v : e[u]) {
        if (v == p) {
            continue;
        }
        int dpu = dp[u];
        int dpv = dp[v];
        int sumu = sum[u];
        int sumv = sum[v];
        
        sum[u] -= dp[v];
        dp[u] = std::max(a[u], sum[u] - a[u]);
        sum[v] += dp[u];
        dp[v] = std::max(a[v], sum[v] - a[v]);
        
        dfs2(v, u);
        
        dp[u] = dpu;
        dp[v] = dpv;
        sum[u] = sumu;
        sum[v] = sumv;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> n;
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    std::string S;
    std::cin >> S;
    for (int i = 0; i < n; i++) {
        a[i] = S[i] - '0';
    }
    
    for (int i = 0; i < n; i++) {
        for (int j : e[i]) {
            ans = std::max(ans, a[i] + a[j]);
        }
    }
    
    dfs(0, -1);
    dfs2(0, -1);
    
    std::cout << ans << "\n";
        
    return 0;
}

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