Submission #958892

#TimeUsernameProblemLanguageResultExecution timeMemory
958892pccPower Plant (JOI20_power)C++17
100 / 100
116 ms28956 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 2e5+10; int dp[mxn]; string s; vector<int> tree[mxn]; int N; int ans = 0; void dfs(int now,int par){ dp[now] = s[now]-'0'; int mx = 0,down = 0; for(auto nxt:tree[now]){ if(nxt == par)continue; dfs(nxt,now); mx = max(mx,dp[nxt]); down += max(dp[nxt],0); } ans = max({mx+dp[now],down-dp[now],ans}); dp[now] = max(dp[now],down-dp[now]); return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; for(int i = 1;i<N;i++){ int a,b; cin>>a>>b; tree[a].push_back(b); tree[b].push_back(a); } cin>>s; s = "#"+s; dfs(1,1); cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...