Submission #498908

#	Time	Username	Problem	Language	Result	Execution time	Memory
498908		khoabright	Power Plant (JOI20_power)	C++17	100 / 100	174 ms	32388 KiB

power

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()

const int N = 2e5 + 5;
int dp[N], sig[N];
vector<int> g[N];

int ans = 0;

void dfs(int u, int p) {
    int sum = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        sum += dp[v];
        ans = max(ans, dp[v] + sig[u]);
    }
    dp[u] = max(sig[u], sum - sig[u]);
    ans = max(ans, dp[u]);
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s; cin >> s;
    rep(i, 1, n) sig[i] = s[i - 1] - '0';
    dfs(1, 0);
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53