Laskettelukeskus

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll c[100001];
ll c2[100001];
int par[100001]; // tree (parent)
pair<int,int> ar[100000]; // tree (depth, index)
 
ll ans;
 
int main() {
  cin >> n;
  for (int i=0; i < n-1; i++) {
    int a, b;
    cin >> a >> b;
    if (par[b-1]) {
      while (true);
    }
    par[b-1] = a;
  }
  for (int i=0; i < n; i++) {
    cin >> c[i];
    ar[i].second = i;
  }
 
  // depth tree
  ar[0].first = -1;
  stack<int> st;
  for (int i=1; i < n; i++) {
    if (ar[i].first == 0) {
      st.push(ar[i].second);
      while (!st.empty()) {
        int ind = st.top();
        int pind = par[ind]-1;
        int d = ar[pind].first;
        if (d == 0) {
          st.push(pind);
        } else {
          ar[ind].first = d - 1;
          st.pop();
        }
      }
    }
  }
  sort(ar, ar + n);
 
  // algorithm
  for (int i=0; i < n; i++) {
    int ind = ar[i].second;
    int pind = par[ind]-1;
    ll dif = c[ind] - c2[ind];
    if (dif > 0) {
      ans += dif;
      c2[ind] += dif;
    }
    c2[pind] += c2[ind];
  }
  
  cout << ans;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED