Submission #4036092

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

void update(const vector<vi> &chi, vi &v, int x) {
  REP(i, SZ(chi[x])) {
    if(v[chi[x][i]] == INT_MAX) v[chi[x][i]] = v[x];
    update(chi, v, chi[x][i]);
  }
}

void propagate(const vector<vi> &chi, vi &v, int x) {
  if(SZ(chi[x]) != 0) {
    int mi = INT_MAX;
    REP(i, SZ(chi[x])) {
      propagate(chi, v, chi[x][i]);
      mi = min(mi, v[chi[x][i]]);
    }
    v[x] = mi;
  }
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n, m; cin >> n >> m;
  vector<int> par(n);
  FOR(i, 1, n) cin >> par[i];
  vector<vi> chi(n);
  FOR(i, 1, n) {
    chi[par[i]].pb(i);
  }
  vi v(n, INT_MAX);
  v[0] = 0;
  REP(i, m) {
    int b, c; cin >> b >> c;
    v[b] = c;
  }

  update(chi, v, 0);
  
  propagate(chi, v, 0);
  v[0] = 0;
  
  
  ll cnt = 0;
  FOR(i, 1, n) {
    cnt += v[i] - v[par[i]];
  }
  cout << cnt << endl;
}

Submission Info

Judge Result