Submission #864327

#	Time	Username	Problem	Language	Result	Execution time	Memory
864327		epicci23	Power Plant (JOI20_power)	C++17	100 / 100	127 ms	29648 KiB

power

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 2e5 + 5;

vector<int> v[N];
string s;
int dp[N];
int ans;
void dfs(int c,int p){
  int cur=0,sum=0;
  for(int x:v[c]){
    if(x==p) continue;
    dfs(x,c);
    cur=max(cur,dp[x]);
    sum+=dp[x];
  }

  if(s[c]=='1'){
  	ans=max(ans,sum-1);
  	ans=max(ans,cur+1);
  	ans=max(ans,1LL);
  }
  else ans=max(ans,sum);
  
  if(s[c]=='1') dp[c]=max(1LL,sum-1);
  else dp[c]=sum;
}

void solve(){
  int n;
  cin >> n;
  
  for(int i=1;i<n;i++){
    int a,b;
    cin >> a >> b;
    v[a].pb(b);
    v[b].pb(a);
  }
  
  cin >> s;
  s = " " + s;
  
  dfs(1,0);
  
  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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