제출 #1343813

#제출 시각아이디문제언어결과실행 시간메모리
1343813khanhphucscratchPower Plant (JOI20_power)C++20
100 / 100
119 ms26896 KiB
#include<bits/stdc++.h>
using namespace std;
vector<int> ad[200005];
int dp[200005], a[200005], ans = 0;
bool visited[200005];
void dfs(int u)
{
    visited[u] = 1;
    for(int v : ad[u]) if(visited[v] == 0){
        dfs(v); dp[u] += dp[v];
    }
    if(a[u] == 1){
        dp[u] = max(dp[u] - 1, 1); ans = max(ans, 1);
        for(int v : ad[u]) if(visited[v] == 0) ans = max(ans, dp[v] + 1);
        ans = max(ans, dp[u]);
    }
    else ans = max(ans, dp[u]);
    visited[u] = 0;
    //cerr<<"A"<<u<<" "<<dp[u]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    for(int i = 0; i < n-1; i++){
        int u, v; cin>>u>>v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    int num = 0;
    for(int i = 1; i <= n; i++){
        char x; cin>>x;
        a[i] = (x == '1'); num += a[i];
    }
    dfs(1);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...