Submission #568058

#	Time	Username	Problem	Language	Result	Execution time	Memory
568058		fadi57	Power Plant (JOI20_power)	C++14	100 / 100	297 ms	32364 KiB

power

#include<bits/stdc++.h>
using namespace std;
const int mx=2e5+5;
vector<int>adj[mx];
int mark[mx];
int ans;
int dp[mx];
 void dfs(int node,int par){

     int sum=0;
     int maxi=0;
    for(auto it:adj[node]){
        if(it!=par){
            dfs(it,node);
            sum+=dp[it];
            maxi=max(maxi,dp[it]);
        }

    }

    if(mark[node]){
      ans=max(ans,maxi+1);
        dp[node]=max(sum-1,1);

    }else{
      dp[node]=sum;
    }
ans=max(ans,dp[node]);

}
int main(){
int n;cin>>n;
 for(int i=0;i<n-1;i++){
        int x,y;
    cin>>x>>y;
    x--;y--;
    adj[x].push_back(y); adj[y].push_back(x);
 }
 string x;cin>>x;
  for(int i=0;i<n;i++){
    mark[i]=(x[i]=='1');
  }
  /*
  for(int i=0;i<n;i++){
    if(mark[i]){

        dfs(i,i);
    }
  }*/
  dfs(0,-1);
  cout<<ans;
}

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