제출 #1191966

#제출 시각아이디문제언어결과실행 시간메모리
1191966SebPower Plant (JOI20_power)C++20
0 / 100
3 ms4936 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<ll>;
using pll = pair<ll,ll>;

#define pb push_back
#define MP make_pair
#define f first
#define s second
#define mid ((l+r)>>1)
#define SZ(x) (int)(x.size())
#define MP make_pair
#define all(x) x.begin(), x.end()

const ll MAXN = 2e5 + 5;
const ll MOD = 998244353;
const ll INF = 1e16;

ll N, ans;
string S;
vll g[MAXN];
ll dp[MAXN], dp2[MAXN];

void solve(ll nodo, ll p) {
    if (S[nodo - 1] == '1') { dp2[nodo] = 1; dp[nodo] = -1; }
    else { dp[nodo] = dp2[nodo] = 0; }

    for (auto &it : g[nodo]) {
        if (it == p) continue;
        solve(it, nodo);

        dp2[nodo] = max(dp2[nodo], dp2[it]);

        dp[nodo] = max(dp[nodo], dp[nodo] + dp[it]);
    }
    if (S[nodo - 1] == '1') dp[nodo] = max(dp[nodo], 1LL);
    else dp[nodo] = max(dp[nodo], 0LL);

    dp2[nodo] = max(dp2[nodo], dp[nodo]);
}

void dfs(ll nodo, ll p) {
    if (nodo == p) solve(nodo, p);
    else {
        // recalcula del padre

        ll aux = -1;
        dp[p] = 1;
        for (auto &it : g[p]) {
            if (it == nodo) continue;

            dp[p] = max(dp[it], dp[p]);

            aux += dp[it];
        }
        dp[p] = max(dp[p], aux);

        // recalcula del nodo

        aux = -1;
        dp[nodo] = 1;
        for (auto &it : g[nodo]) {
            dp[nodo] = max(dp[it], dp[nodo]);

            aux += dp[it];
        }
        dp[nodo] = max(dp[nodo], aux);
    }

    ans = max(ans, dp[nodo]);

    for (auto &it : g[nodo]) {
        if (it == p) continue;
        dfs(it, nodo);
    }
}


void tc() {
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        ll a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin >> S;

    //dfs(1, 1);
    for (int i = 1; i <= N; i++) {
        solve(i, i);
        ans = max(ans, dp2[i]);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    while (t--) tc();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...