Submission #928635

#	Time	Username	Problem	Language	Result	Execution time	Memory
928635		1075508020060209tc	Power Plant (JOI20_power)	C++14	100 / 100	192 ms	25620 KiB

power

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define _int __int128
#define int long long
int n;
vector<int>e[200005];
int dp[200005];
int ar[200005];
void init(){
cin>>n;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b;
    e[a].push_back(b);
    e[b].push_back(a);
}
string s;
cin>>s;
for(int i=0;i<n;i++){
    ar[i+1]=s[i]-'0';
}
}
int ans;
void dfs(int nw,int pa){
for(auto v:e[nw]){
    if(v==pa){continue;}
    dfs(v,nw);
}
if(ar[nw]==0){
for(auto v:e[nw]){
    if(v==pa){continue;}
    dp[nw]+=dp[v];
}
}else{
dp[nw]=-1;
for(auto v:e[nw]){
    if(v==pa){continue;}
    dp[nw]+=dp[v];
    ans=max(ans,dp[v]+1);
}
dp[nw]=max(1ll,dp[nw]);
}
ans=max(ans,dp[nw]);
}


signed main(){
init();
dfs(1,0);
cout<<ans;

}

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