제출 #1210591

#제출 시각아이디문제언어결과실행 시간메모리
1210591Double_SlashPower Plant (JOI20_power)C++20
100 / 100
142 ms25840 KiB
#include <bits/stdc++.h>

using namespace std;
 
int n, m, s[200001], ans;
vector<int> adj[200001];

int dfs(int i, int p = 0) {
    int dp = -s[i], mx = 0;
    for (int j: adj[i]) {
        if (j == p) continue;
        int cur = dfs(j, i);
        dp += cur;
        mx = max(mx, cur);
    }
    ans = max({ans, dp, mx + s[i]});
    return max(dp, s[i]);
}

int main() {
    cin >> n;
    for (int i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        s[i] = c == '1';
    }
    dfs(1, 0);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...