Submission #599287

#TimeUsernameProblemLanguageResultExecution timeMemory
599287JomnoiPower Plant (JOI20_power)C++17
100 / 100
218 ms29260 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5 + 5; int ans; vector <int> graph[MAX_N]; int power[MAX_N]; int dp[MAX_N]; void dfs(int u, int p) { int ma = 0; for(auto v : graph[u]) { if(v == p) { continue; } dfs(v, u); ma = max(ma, dp[v]); dp[u] += dp[v]; } dp[u] = max(dp[u] - power[u], power[u]); ans = max({ans, dp[u], ma + power[u]}); } int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; for(int i = 1; i <= N - 1; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } for(int i = 1; i <= N; i++) { char c; cin >> c; power[i] = c - '0'; } dfs(1, -1); cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...