Submission #782954

#	Time	Username	Problem	Language	Result	Execution time	Memory
782954		Kahou	Power Plant (JOI20_power)	C++14	100 / 100	112 ms	30068 KiB

power

/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
int n, dp[N][2];
int mark[N];
vector<int> adj[N];

void dfs(int u, int p=0) {
        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
                dp[u][0] = max(dp[u][0], max(dp[v][0], dp[v][1]+mark[u]));
                dp[u][1] += dp[v][1];
        }
        dp[u][1] = max(dp[u][1]-mark[u], mark[u]);
        dp[u][0] = max(dp[u][0], dp[u][1]);
}
void solve() {
        cin >> n;
        for (int i = 1; i <= n-1; 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 c;
                cin >> c;
                mark[i] = c-'0';
        }
        dfs(1);
        cout << dp[1][0] << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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