Submission #1152890

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