Submission #1097080

#TimeUsernameProblemLanguageResultExecution timeMemory
1097080anmattroiPower Plant (JOI20_power)C++14
100 / 100
83 ms28760 KiB
#include <bits/stdc++.h>

#define maxn 200005

using namespace std;

int n;
vector<int> adj[maxn];
int f[maxn], g[maxn];

char a[maxn];
int ds = 0;
int E[maxn];


void dfs(int u, int dad) {
    int sum = 0, mx = 0;
    for (int v : adj[u]) {
        if (v == dad) continue;
        dfs(v, u);
        mx = max(mx, f[v]);
        sum += f[v];
    }
    if (E[u] == 1) ds = max(ds, max(mx+1, sum-1));
    else ds = max(ds, sum);
    f[u] = max(E[u], sum-E[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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++) {
        cin >> a[i];
        if (a[i] == '1') E[i] = 1;
    }
    dfs(1, 0);
    cout << ds;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...