Submission #928635

#TimeUsernameProblemLanguageResultExecution timeMemory
9286351075508020060209tcPower Plant (JOI20_power)C++14
100 / 100
192 ms25620 KiB
//#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;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...