제출 #1208225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208225		minhpk	Power Plant (JOI20_power)	C++20	100 / 100	81 ms	46268 KiB

power

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
vector<int> z[1000005];
int open[1000005];
int dp[1000005];
int dist[1000005];
int max1;
void dfs(int i,int par){
    dist[i]=dist[par]+open[par];
    if (open[i]){
        dp[i]=1;
    }
    int pre=0;
    for (auto p:z[i]){
         if (p==par){
            continue;
         }
         dfs(p,i);

         pre+=dp[p];
    }
    int pl=0;
    pre-=open[i];
    dp[i]=max(dp[i],pre);
    max1=max(max1,dp[i]+(dist[i]>0));
}

signed main()
{
   // freopen("test.txt", "r", stdin);
   // freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    string s;
    cin >> s;
    s='#'+s;
    for (int i=1;i<=a;i++){
         open[i]=s[i]-'0';
       //  cout << open[i] << " " << "\n";
    }
    dfs(1,0);

    for (int i=1;i<=a;i++){
         max1=max(max1,dp[i]);
    }
   // cout << dp[3] << "\n";
    cout << max1 << "\n";
    return 0;
}






/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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