Submission #572015

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
#define int long long
const int MAX_V = 100000;
const int INF = (int)1e9;
struct BIT {
  int N;
  vector<int> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, int w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  int sum(int a) {
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
};
struct Counter {
  const int N;
  BIT bit;
  Counter(int n) : N(n), bit(n) {}
  void insert(int x) {
    bit.add(x, 1);
  }
  void drop(int x) {
    bit.add(x, -1);
  }
  int geq(int i) {
    return bit.sum(N) - bit.sum(i);
  }
};
int N;
int L[MAX_V], P[MAX_V], D[MAX_V], M[MAX_V];
vector<int> child[MAX_V];
map<int, int> cmp;
map<int, int> ans;
void dfs(int v, Counter &counter) {
  for(int c : child[v]) counter.insert(cmp[M[c]]);
  auto it = cmp.upper_bound(D[v]);
  int geq = 0;
  if(it != cmp.end()) {
    geq = counter.geq(it->second);
  }
  if(!ans.count(D[v])) {
    ans[D[v]] = geq;
  }
  else {
    ans[D[v]] = min(ans[D[v]], geq);
  }
  for(int c : child[v]) {
    counter.drop(cmp[M[c]]);
    dfs(c, counter);
    counter.insert(cmp[M[c]]);
  }
  for(int c : child[v]) counter.drop(cmp[M[c]]);
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> N;
  REP(i,N) cin >> L[i];
  P[0] = -1;
  for(int i = 1; i < N; ++i) {
    cin >> P[i]; P[i]--;
    child[P[i]].push_back(i);
  }
  D[0] = L[0];
  for(int i = 1; i < N; ++i) {
    D[i] = D[P[i]] + L[i];
  }
  for(int i = N - 1; i >= 0; --i) {
    M[i] = D[i];
    for(int c : child[i]) {
      M[i] = max(M[i], M[c]);
    }
  }
  REP(i,N) cmp[M[i]] = -1;
  {
    int i = 0;
    for(auto &it : cmp) it.second = i++;
  }
  Counter counter(cmp.size());
  dfs(0, counter);
  int Q; cin >> Q;
  REP(q,Q) {
    int H; cin >> H;
    if(!ans.count(H)) cout << -1 << endl;
    else cout << ans[H] << endl;
  }
}

Submission Info

Judge Result