Submission #869768

#TimeUsernameProblemLanguageResultExecution timeMemory
869768serifefedartarPower Plant (JOI20_power)C++17
100 / 100
111 ms30212 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9+9; const ll LOGN = 30; const ll MAXN = 2e5 + 100; const ll MULT = 1e9; vector<vector<int>> graph; int here[MAXN], sub[MAXN], par[MAXN]; int ans = 0; void dfs(int node, int parent) { int sum = 0; for (auto u : graph[node]) { if (u == parent) continue; dfs(u, node); sum += sub[u]; } sub[node] = max(here[node], sum - here[node]); } void dfs2(int node, int parent) { int sum = 0; for (auto u : graph[node]) { if (u != parent) sum += sub[u]; } sum += par[node]; for (auto u : graph[node]) { if (u != parent) par[u] = max(here[node], sum - sub[u] - here[node]); } for (auto u : graph[node]) { if (u == parent) continue; dfs2(u, node); } } int main() { fast int N, A, B; cin >> N; graph = vector<vector<int>>(N+1, vector<int>()); for (int i = 1; i < N; i++) { cin >> A >> B; graph[A].push_back(B); graph[B].push_back(A); } for (int i = 1; i <= N; i++) { char ch; cin >> ch; here[i] = ch - '0'; } dfs(1, 1); dfs2(1, -1); for (int i = 1; i <= N; i++) ans = max(ans, sub[i] + par[i]); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...