Submission #359345

#	Time	Username	Problem	Language	Result	Execution time	Memory
359345		eyangch	Power Plant (JOI20_power)	C++17	100 / 100	192 ms	28396 KiB

power

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int N;
vector<int> graph[200000];
char s[200001];
bool vis[200000];
int ans = 0;

int dfs(int id, int par){
    assert(!vis[id]);
    vis[id] = true;
    int p = s[id] - '0';
    int ret = p;
    int c = 0;
    int mxc = 0;
    for(int i : graph[id]){
        if(i == par) continue;
        int cur = dfs(i, id);
        if(cur == 0) continue;
        c++;
        mxc = max(mxc, cur);
        ret += cur;
    }
    if(p && c > 0){
        if(c == 1){
            ans = max(ans, ret);
            ret -= 2;
        }else{
            ret -= 2;
            ans = max(ans, max(ret, mxc+1));
        }
    }
    ans = max(ans, ret);
    return max(p, ret);
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < N-1; i++){
        int a, b; cin >> a >> b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }
    cin >> s;
    dfs(0, 0);
    cout << ans << endl;
}

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