Submission #1152886

#TimeUsernameProblemLanguageResultExecution timeMemory
1152886Hamed_GhaffariPower Plant (JOI20_power)C++20
0 / 100
2 ms5008 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...