Submission #803439

#TimeUsernameProblemLanguageResultExecution timeMemory
803439khoquennguoiminhthuongPower Plant (JOI20_power)C++14
100 / 100
107 ms28112 KiB
#include <bits/stdc++.h> using namespace std; int n; vector<int>g[200005]; string s; int a[200005]; int dp[200005]; int ans=0; int dfs(int u,int pa) { int sum1=0,sum2=0; for(auto v:g[u]) if(v!=pa) { int t=dfs(v,u); sum1=max(sum1,t); sum2+=max(0,t); } ans=max(ans,sum1+a[u]); ans=max(ans,sum2-a[u]); return max(sum2-a[u],a[u]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1; i<n; i++) { int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } cin>>s; for(int i=0; i<n; i++)if(s[i]=='1')a[i+1]=1; dfs(1,0); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...