Laskettelukeskus

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

const int N = 1e5+5;

vector<int> v[N], c(N);
int total;

void calc(int s, int k) {
    int need = 0;
    for (int u : v[s]) need += c[u];
    total = max(total, need-k); 
    for (int u : v[s]) {
        calc(u, c[u]);
    }
}

bool ok(int k) {
    total = 0;
    calc(1, c[1]);
    return total <= k;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; ++i) 
        cin >> c[i];
    
    int lb = 0, rb = 1e9;
    while (lb <= rb) {
        int mid = (lb + rb) / 2;
        if (!ok(mid)) 
            lb = mid + 1;
        else
            rb = mid - 1;
    }
    cout << lb << '\n';
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 2

Verdict: WRONG ANSWER

Test 5

Group: 2

Verdict: WRONG ANSWER

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 1, 2

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 1, 2

Verdict: WRONG ANSWER

Test 13

Group: 2

Verdict: WRONG ANSWER