Submission #1212610

#TimeUsernameProblemLanguageResultExecution timeMemory
1212610vyaductPower Plant (JOI20_power)C++20
0 / 100
3 ms4928 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(c) (c).begin(), (c).end() #define sz(c) (int)(c).size() #define vt vector #define pb push_back #define F first #define S second #define pll pair<ll,ll> #define MP make_pair const int mxN = 200'001; vt<int> adj[mxN]; bool power[mxN]; int dp[mxN]; int ans=0; void dfs(int s, int e) { if (power[s]){ int cur=0; for (int u: adj[s]){ if (u == e) continue; dfs(u, s); dp[s]+=dp[u]; cur=max(cur,dp[u]+1); } ans=max(ans,cur); dp[s]--; dp[s]=max(dp[s], 1); } else { for (int u: adj[s]){ if (u == e) continue; dfs(u, s); dp[s]+=dp[u]; } ans=max(ans,dp[s]); } } void solve(){ int n; cin>>n; for (int i=0;i<n-1;i++){ int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } string s; cin>>s; for (int i=1;i<=n;i++) {power[i]=s[i-1]=='1';} dfs(1, 0); cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...