Source Code
#include <bits/stdc++.h>
#define endl "\n"
#define debug(a) cout << #a << ": " << a << endl
#define debugLine() cout << "==============" << endl
#define tick() cout << "Tick" << endl
#define testCases() int t; cin >> t; while(t--)
#define all(a) a.begin(), a.end()
#define fillWith(a, b) memset(a, b, sizeof(a))
#define Mod 1000000007
#define goFast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define files(x) freopen(x, "r", stdin)
typedef long long ll;
using namespace std;

#define int long long

vector<int> myGraph[200005];

multiset<int> st[200005];
int personality[200005];

map<pair<int, int>, int> rankPer;
int mp[200005];

void dfs(int u, int counter = 0) {
    st[counter].insert(personality[u]);
    mp[u] = counter;
    if(rankPer[{counter, personality[u]}] == 0) {
        rankPer[{counter, personality[u]}] = u;
    }
    else {
        rankPer[{counter, personality[u]}] = min(rankPer[{counter, personality[u]}], u);
    }
    for (int v : myGraph[u])
        dfs(v, counter + 1);
}

main() {
    goFast();
    int N;
    cin >> N;
    for(int i = 1; i <= N - 1; i++) {
        int x;
        cin >> x;
        myGraph[x].push_back(i + 1);
    }
    for(int i = 1; i <= N; i++) {
        cin >> personality[i];
    }
    dfs(1);
    int answers[N + 3] = {0};
    for(int i = 1; i <= N; i++) {
        int rank = mp[i];
        if(st[rank + 4].empty()) continue;
        auto it1 = st[rank + 4].upper_bound(personality[i]);
        if(it1 == st[rank + 4].end()) {
            it1--;
            answers[i] = rankPer[{rank + 4, *it1}];
        }
        else {
            int x1 = (*it1);
            if(it1 != st[rank + 4].begin()) {
                auto it2 = it1;
                it2--;
                int x2 = (*it2);
                if(abs(personality[i] - x1) > abs(personality[i] - x2)) {
                    answers[i] = rankPer[{rank + 4, (*it2)}];
                }
                else if(abs(personality[i] - x1) < abs(personality[i] - x2)) {
                    answers[i] = rankPer[{rank + 4, (*it1)}];
                }
                else {
                    answers[i] = min(rankPer[{rank + 4, *it1}], rankPer[{rank + 4, *it2}]);
                }
            }
            else {
                answers[i] = rankPer[{rank + 4, (*it1)}];
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        cout << answers[i] << " ";
    }
    cout << endl;
}
Copy
Find a Friend AhmadShahal
GNU G++17
15 ms
14.9 MB
Wrong Answer