Source Code
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

const int N=2e5+5;
const int LOG=19;
int n;
vector<vector<int>>up(N,vector<int>(LOG));
vector<int>depth(N),adj[N],p(N);
 
void calcDepthAndKth(int v, int p){
	for(auto u:adj[v]){
        if(u==p) continue;
		depth[u]=depth[v]+1;
		up[u][0]=v;
		for(int i=1;i<LOG;i++){
			up[u][i]=up[up[u][i-1]][i-1];
		}
		calcDepthAndKth(u,v);
	}
}
 
int getKth(int node, int k){
	if(k>depth[node]) return -1;
	for(int i=0;i<LOG;i++){
		if((1<<i)&k){
			node=up[node][i];
		}
	}
	return node;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    for(int i=1,x;i<n;i++){
        cin>>x;
        adj[x-1].push_back(i);
    }

    for(int i=0;i<n;i++){
        cin>>p[i];
    }

    calcDepthAndKth(0,-1);

    vector<int>ans(n,-1);

    for(int i=0;i<n;i++){
        int forthP=getKth(i,4);
        if(forthP==-1) continue;
        if(ans[forthP]==-1){
            ans[forthP]=i;
        } else if(abs(p[i]-p[forthP])==abs(p[ans[forthP]]-p[forthP])){
            if(i<ans[forthP]){
                ans[forthP]=i;
            }
        } else if(abs(p[i]-p[forthP])<abs(p[ans[forthP]]-p[forthP])){
            ans[forthP]=i;
        }
    }

    for(int i=0;i<n;i++){
        cout<<ans[i]+1<<' ';
    }
}
Copy
Find a Friend YazanIstatiyeh
GNU G++17
186 ms
46.4 MB
Accepted