제출 #1141017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141017		dombly	Power Plant (JOI20_power)	C++20	100 / 100	146 ms	30908 KiB

power

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N = 3e5 + 10;
const int inf = 2e15;
const int mod = 1e9 + 7;

int dp[N],a[N],ans = 0;
string s;
vector<int>g[N];

void Dfs(int x,int par) {
    int mx = 0;
    for(int j : g[x]) {
        if(j != par) {
            Dfs(j,x);
            dp[x] += dp[j];
            mx = max(mx,dp[j]);
        }
    }
    dp[x] = max(dp[x] - a[x],a[x]);
    ans = max(ans,max(dp[x],mx + a[x]));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    cin >> s;
    s = '.' + s;
    for(int i = 1; i <= n; i++) a[i] = s[i] - '0';
    Dfs(1,0);
    cout << ans;
    return 0;
}

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