제출 #626553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626553		NKIAMHAD	Power Plant (JOI20_power)	C++14	100 / 100	171 ms	39436 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
#define f first
#define s second
#define lid(x) (x*2)
#define rid(x) (1+x*2)
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
const ll maxn = 5e5+55;
const ll max2 = 1e6+55;
const ll inf = 1e9;
const ll lg = 17;
const ll base = 101;
const ll modn = 998244353;
const ll mod2 = 1e9+9;

ll T, len, que, num, sum, x, fir, sec;
vector <ll> G[maxn];
ll dp[maxn][2];
string s;

void dfs(ll x, ll last) {
    if(s[x-1] == '1') {
        ll sigma = 0, max0 = 0, max1 = 0;
        for(ll ver : G[x]) {
            if(ver == last)
                continue;
            dfs(ver, x);
            sigma += dp[ver][1], max0 = max(max0, dp[ver][0]), max1 = max(max1, dp[ver][1]);
        }
        dp[x][0] = max(1, max(sigma-1, max(max0, max1+1)));
        dp[x][1] = max(1, sigma-1);
        return;
    }
    ll sigma = 0, max0 = 0, max1 = 0;
    for(ll ver : G[x]) {
        if(ver == last)
            continue;
        dfs(ver, x);
        sigma += dp[ver][1], max0 = max(max0, dp[ver][0]), max1 = max(max1, dp[ver][1]);
    }
    dp[x][0] = max(max0, sigma);
    dp[x][1] = sigma;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> len;
    for(int i=1 ; i<len ; i++)
        cin >> fir >> sec, G[fir].pb(sec), G[sec].pb(fir);
    cin >> s;
    dfs(1, 0);
    cout << dp[1][0];


    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53