Source Code
#ifndef Local
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("popcnt,abm,mmx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;

#define popCnt(x) (__builtin_popcountll(x))
#define sz(x) ((int)(x.size()))
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define rep(i, l, r) for (int i = l; i < r; ++i)
using Long = long long;
using Double = double;
using vi = vector<int>;

template <class U, class V>
istream& operator>>(istream& is, pair<U, V>& p) {
  is >> p.first >> p.second;
  return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : v) {
    is >> x;
  }
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (auto& x : v) {
    os << x << " ";
  }
  return os;
}

const int N = 2e5 + 5;
int p[N], manager[N], res[N];
vi children[N];

void update(int m, int junior) {
  if (res[m] == 0 || make_pair(abs(p[m] - p[junior]), junior) < make_pair(abs(p[m] - p[res[m]]), res[m])) {
    res[m] = junior;
  }
}

void dfs(int node) {
  static vi ancestors;
  ancestors.emplace_back(node);
  int four_up_level = sz(ancestors) - 5;
  if (four_up_level >= 0) {
    update(ancestors[four_up_level], node);
  }
  for (int v: children[node]) {
    dfs(v);
  }
  ancestors.pop_back();
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#else
#define endl '\n'
#endif
  int n;
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    cin >> manager[i];
    children[manager[i]].emplace_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
  }
  dfs(1);
  for (int i = 1; i <= n;++i){
    cout << res[i] << " ";
  }
  cout << endl;
  return 0;
}
Copy
Find a Friend Mohammad_Yasser
GNU G++17
106 ms
23.6 MB
Accepted