Submission #992599

#	Time	Username	Problem	Language	Result	Execution time	Memory
992599		vysniak_grossmeister	Power Plant (JOI20_power)	C++17	100 / 100	68 ms	35728 KiB

power

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
using namespace std;

const int N = 1e5 * 5ll;

typedef long long ll;
string s;
vector<ll>g[N];

ll ans = 0ll;

ll dp[N];

void dfs(ll v, ll p){

    if(s[v - 1] == '1'){

        for(auto to : g[v]){


            if(to != p){

                dfs(to, v);

                dp[v] = dp[v] + dp[to];

                // just take subtree of child so ->>...

                ans = max(ans, dp[to] + 1ll);


            }




        }

        if(dp[v] >= 2ll){

            dp[v] -= 1ll;

        }
        else{

            dp[v] = max(dp[v], 1ll);

        }

        // because v will break;

    }
    else{

        for(auto to : g[v]){

            if(to != p){

                dfs(to, v);

                dp[v] += dp[to];

                // just take subtree of child so ->>...

                ans = max(ans, dp[to] + 0ll);

            }

        }


    }

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

}



int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

ll n;
cin >> n;

for(ll i = 1; i <= n - 1; ++i){
    ll a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
}


cin >> s;

dfs(1ll, -1ll);

cout << ans << endl;

return 0;

}

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