Submission #502471

#TimeUsernameProblemLanguageResultExecution timeMemory
502471tengiz05Power Plant (JOI20_power)C++17
100 / 100
195 ms33100 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...