Submission #511810

#	Time	Username	Problem	Language	Result	Execution time	Memory
511810		czhang2718	Power Plant (JOI20_power)	C++17	100 / 100	286 ms	30400 KiB

power

#include "bits/stdc++.h"
using namespace std;

const int N=200001;

int n;
vector<int> adj[N];
int dp[N][2];
int up[N];
string s;
int ans=1;

void dfs(int x, int par){
  dp[x][1]=(s[x]=='1'?1:-1e9);
  dp[x][0]=(s[x]=='1')*(-1);
  for(int k:adj[x]){
    if(k==par) continue;
    dfs(k, x);
    dp[x][0]+=max({0, dp[k][0], dp[k][1]});
    if(s[x]=='1' && s[k]=='1') ans=max(ans, 2);
  }
  // cout << "dp[" << x << "][" << 0 << "] " << dp[x][0] << '\n';
}

void dfs2(int x, int par){
  up[x]=max(up[x], 0);
  // cout << "up " << x << " " << up[x] << "\n";
  int sum=up[x];
  for(int k:adj[x]){
    if(k==par) continue;
    sum+=max({0, dp[k][0], dp[k][1]});
  }
  for(int k:adj[x]){
    if(k==par) continue;
    up[k]=max(dp[x][1], (s[x]=='1')*(-1)+sum-max({0, dp[k][0], dp[k][1]}));
    dfs2(k, x);
    ans=max(ans, dp[k][0]+up[k]);
  } 
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for(int i=1; i<n; i++){
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  cin >> s;
  s='0'+s;

  dfs(1, 0);
  dfs2(1, 0);
  cout << ans;
}

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