제출 #1282965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282965		dhuyyyy	Power Plant (JOI20_power)	C++20	100 / 100	151 ms	28224 KiB

power

 #include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,4>;

const int N = 2e5+5;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int base = 31;

int n, u, v, ans = 0;

int gen[N], dp[N];

char c;

vector <int> adj[N];

void dfs(int u,int p){
    for (int it : adj[u]){
        if (it == p) continue;
        dfs(it,u);
        dp[u] += dp[it];
        ans = max(ans,dp[it] + gen[u]);
    }
    dp[u] = max(dp[u] - gen[u],gen[u]);
    ans = max(ans,dp[u]);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++){
        cin >> c;
        gen[i] = (c - '0');
    }
    dfs(1,0);
    cout << ans;
    return 0;
}

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