Submission #1152890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152890		Hamed_Ghaffari	Power Plant (JOI20_power)	C++20	100 / 100	97 ms	26044 KiB

power

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

#define pb push_back
#define maxs(a,b) (a=max(a,b))

const int MXN = 2e5+5;

int n;
vector<int> g[MXN];
int dp[MXN], ans;
string s;

void dfs(int v, int p=0) {
    for(int u : g[v])
        if(u!=p)
            dfs(u, v),
            dp[v] += dp[u],
            maxs(ans, dp[u]+(s[v]-'0'));
    maxs(ans, dp[v] = max(dp[v]-(s[v]-'0'), s[v]-'0'));
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1,u,v; i<n; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> s;
    s = "0" + s;
    dfs(1);
    cout << ans << '\n';
    return 0;
}

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