Submission #1212616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212616		vyaduct	Power Plant (JOI20_power)	C++20	0 / 100	3 ms	4928 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define all(c) (c).begin(), (c).end()
#define sz(c)  (int)(c).size()
#define vt vector
#define pb push_back
#define F first
#define S second
#define pll pair<ll,ll>
#define MP make_pair

const int mxN = 200'005;
vt<int> adj[mxN];
bool power[mxN];
ll dp[mxN];
ll ans=0;

void dfs(int s, int e) {
  dp[s]=0;
  if (power[s]){
    ll cur=0;
    for (int u: adj[s]){
      if (u == e) continue;
      dfs(u, s);
      dp[s]+=dp[u];
      cur=max(cur,dp[u]+1);
    }
    ans=max(ans,cur);
    dp[s]--;
    dp[s]=max(dp[s], 1LL);
  } else {
    for (int u: adj[s]){
      if (u == e) continue;
      dfs(u, s);
      dp[s]+=dp[u];
    }
    ans=max(ans,dp[s]);
  }
}

void solve(){
  int n; cin>>n;
  for (int i=0;i<n-1;i++){
    int u,v; cin>>u>>v;
    u--,v--;
    adj[u].pb(v); adj[v].pb(u);
  }
  string s; cin>>s;
  for (int i=0;i<n;i++) {power[i]=s[i]=='1';}
  dfs(0, -1);
  cout << ans << '\n';
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

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