Submission #1152886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152886		Hamed_Ghaffari	Power Plant (JOI20_power)	C++20	0 / 100	2 ms	5008 KiB

power

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

#define pb push_back

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);
    for(int u : g[v])
        if(u!=p)
            dp[v] += dp[u];
    ans = max(ans, dp[v]);
    if(s[v]=='1') {
        for(int u : g[v])
            if(u!=p)
                ans = max(ans, dp[u]+1);
        dp[v] = max(1, dp[v]-1);
        ans = max(ans, dp[v]);
    }
}

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: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53