제출 #997331

#제출 시각아이디문제언어결과실행 시간메모리
997331DanielPr8Power Plant (JOI20_power)C++14
100 / 100
80 ms31384 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvl g;
vb gen;
vll dp0, dp1;
ll ans = 0;
void dfs(ll cur, ll par){
    if(!gen[cur]){
        for(ll i:g[cur]){
            if(i==par)continue;
            dfs(i, cur);
            dp0[cur]+=dp0[i];
            dp1[cur] = max(dp1[cur], dp1[i]);
        }
    }
    else{
        ll mx=0;
        for(ll i:g[cur]){
            if(i==par)continue;
            dfs(i, cur);
            dp0[cur]+=dp0[i];
            dp1[cur] = max(dp1[cur], dp1[i]);
            mx = max(mx, dp0[i]);
        }
        dp0[cur] = max(dp0[cur]-1, 1ll);
        dp1[cur] = max(dp1[cur]-1, mx+1);
    }
    ans = max(ans, max(dp0[cur], dp1[cur]));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, a, b; cin >> n;
    g = vvl(n+1, vll());
    gen = vb(n+1);
    dp0=dp1=vll(n+1);
    for(ll i = 0; i < n-1; ++i){
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    string s;
    cin >> s;
    for(ll i = 1; i <= n; ++i)if(s[i-1]=='1')gen[i]=1;
    dfs(1,0);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...