Submission #1197754

#TimeUsernameProblemLanguageResultExecution timeMemory
1197754aykhnPower Plant (JOI20_power)C++20
100 / 100
81 ms48780 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 1e6 + 5; const int mod = 1e9 + 7; int n; vector<int> adj[MXN]; int dp[MXN], val[MXN], sum[MXN]; int res = 0; void dfs(int a, int p) { sum[a] = val[a]; for (int &v : adj[a]) { if (v == p) continue; dfs(v, a); sum[a] += sum[v]; dp[a] += dp[v]; } dp[a] = max(dp[a], sum[a] + val[a]); res = max(res, dp[a] - sum[a]); if (!val[a]) return; for (int &v : adj[a]) { if (v == p) continue; res = max(res, dp[v] - sum[v] + 1); } } void _() { cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++) { char ch; cin >> ch; val[i] = ch - '0'; } dfs(1, 1); cout << res << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) _(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...