Submission #623199

#	Time	Username	Problem	Language	Result	Execution time	Memory
623199		K4YAN	Power Plant (JOI20_power)	C++17	0 / 100	4 ms	5036 KiB

power

//Be Name Khoda

#include<bits/stdc++.h>
//pragma shayad niaz she

using namespace std;

typedef long long ll;
typedef long double ld;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll mxn = 2e5 + 16;
ll n, m, t, q, w, ans;
ll dp[mxn], subt[mxn];
vector<ll> adj[mxn];
bool mark[mxn];
string s;

void input() {

    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> q >> w;
        adj[q].push_back(w);
        adj[w].push_back(q);
    } cin >> s;
    s = '0' + s;

}

void DFS(int v) {
    mark[v] = 1;
    ll cnt = 0, sum = 0;
    if(s[v] == '1') dp[v] = 1, subt[v] = 1;
    for(auto u : adj[v]) {
        if(!mark[u]) {
            DFS(u);
            if(subt[u] > 0) {
                subt[v] += subt[u];
                cnt++, sum += dp[u];
            }
        }
    }
    if(cnt > 1 && s[v] == '1') {
        sum--;
    } 
    dp[v] = max(dp[v], sum); 
    if(cnt == 1 && s[v] == '1') {
        ans = max(ans, dp[v] + 1);
    }
    return;
}

void solve() {

    ll cnt = 0;
    for(auto u : s) {
        if(u == '1') cnt++;
    }
    if(cnt < 3) {
        cout << cnt << "\n";
        return;
    }
    DFS(1);
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

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