Submission #822290

---

Source Code Expand

#include <algorithm>
#include <array>
#include <complex>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline bool valid(const int x, const int r) { return 0 <= x && x < r; }

void initIOStream() {
  ios::sync_with_stdio(false); // stdinなどと同期しない
  cin.tie(0); // cinの前にflushしない
  cout.setf(ios::fixed);
  cout.precision(10); // 四捨五入して指定桁数表示
}

int N, M;
vector<int> P;
vector<int> L;
vector<int> B;
vector<int> C;
vector<int> minv;
vector<vector<int> > G;
int ans;

int func1(int p){
  //cout << "p = "  <<  p << endl;
  int res = 1 << 28;
  if(!L[p]){
    for(int i = 0, size = G[p].size(); i < size; ++i){
      res = min(res, func1(G[p][i]));
    }
  }else{
    res = L[p];
  }
  minv[p] = res;
  return res;
}

void func2(int p, int q){
  if(L[p]){
    return;
  }
  for(int i = 0, size = G[p].size(); i < size; ++i){
    ans += minv[G[p][i]] - q;
    func2(G[p][i], max(minv[G[p][i]], q));
  }
}

int main() {
  initIOStream();

  cin >> N >> M;
  P.resize(N - 1);
  for(int i = 0; i < N - 1; ++i){
    cin >> P[i];
  }
  B.resize(M);
  C.resize(M);
  for(int i = 0; i < M; ++i){
    cin >> B[i] >> C[i];
  }

  G = vector<vector<int> >(N, vector<int>());
  for(int i = 0, size = P.size(); i < size; ++i){
    G[P[i]].emplace_back(i + 1);
  }

  L = vector<int>(N, 0);
  for(int i = 0; i < M; ++i){
    L[B[i]] = C[i];
  }

  // for(const auto& l : L) cout << l << endl;
  // for(int i = 0; i < G.size(); ++i){
  //   cout << i << ": ";
  //   for(const auto& e : G[i]){
  //     cout << e << " ";
  //   }
  //   cout << endl;
  // }
  // return 0;
  minv.resize(N);
  func1(0);
  // for(const auto& v : minv) cout << v << endl;
  ans = 0;
  func2(0, 0);
  cout << ans << endl;
}

Submission Info

Judge Result