제출 #359344

#제출 시각아이디문제언어결과실행 시간메모리
359344eyangchPower Plant (JOI20_power)C++17
47 / 100
226 ms39388 KiB
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

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

int dfs(int id){
    if(vis[id]) return 0;
    vis[id] = true;
    int p = s[id] - '0';
    int ret = p;
    int c = 0;
    int mxc = 0;
    for(int i : graph[id]){
        int cur = dfs(i);
        if(cur == 0) continue;
        c++;
        mxc = max(mxc, cur);
        ret += cur;
    }
    if(p && c > 0){
        if(c == 1){
            ans = max(ans, ret);
            (--ret)--;
        }else{
            (--ret)--;
            ans = max({ans, 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);
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...