Submission #19203171

---

Source Code Expand

#include <iostream>
#include <queue>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> parent(N);
  vector<vector<int>> child(N);
  vector<int> inEdge(N, 0);
  rep(i, N-1) {
    cin >> parent[i+1];
    child[parent[i+1]].emplace_back(i+1);
    inEdge[parent[i+1]]++;
  }
  vector<int64_t> C(N, INT64_MAX);
  C[0] = 0;
  queue<int> que;
  rep(i, M) {
    int b, c;
    cin >> b >> c;
    C[b] = c;
    que.emplace(b);
  }

  while(!que.empty()) {
    int size = que.size();
    rep(i, size) {
      auto u = que.front();
      que.pop();
      if(u == 0) break;
      for(auto& v : child[u]) C[v] -= C[u];
      C[parent[u]] = min(C[parent[u]], C[u]);
      inEdge[parent[u]]--;
      if(inEdge[parent[u]] == 0)
        que.emplace(parent[u]);
    }
  }

  int64_t answer = 0;
  rep(i, N) answer += C[i];
  cout << answer << endl;
  return 0;
}

Submission Info

Judge Result