Submission #19377912

---

Source Code Expand

//#include <atcoder/all>
//using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(v) v.begin(), v.end()
#define bit(n) (1LL<<(n))
#define FIX(d) fixed << setprecision(d)
using P = pair<int, int>;
using LP = pair<ll, ll>;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const ll LINF = (1LL<<60);

int n,m;
Graph G;
vector<int> cnt;

void dfs1(int cur) {
  for(auto nx: G[cur]){
    dfs1(nx);
    chmin(cnt[cur], cnt[nx]);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  G.resize(n);
  FOR(i,1,n){
    int p; cin >> p;
    G[p].push_back(i);
  }
  cnt.assign(n, INF);
  cnt[0] = 0;
  REP(i,m){
    int b,c; cin >> b >> c;
    cnt[b] = c;
  }
  
  dfs1(0);
  
  int ans = 0;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int cur = que.front();
    que.pop();
    for(auto nx: G[cur]){
      ans += cnt[nx] - cnt[cur];
      que.push(nx);
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result