Source Code
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

int n, a[200001], f[200001], ans[200001] = {}, p[200001], cost[200001];
vector<int> v[200001];
vector<vector<int>> level;
void bfs(int src){
	queue<int>q;
	q.push(src);
	vector<int> l;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0; i < v[u].size(); ++i){
			l.push_back(v[u][i]);
			p[v[u][i]] = u;
		}
		if(q.empty()){
			level.push_back(l);
			for(int i = 0; i < l.size(); ++i){
				q.push(l[i]);
			}
			l.clear();
		}
	}
}
int main() {
	cin >> n;
	for(int i = 2; i <= n; ++i){
		cin >> a[i];
		v[a[i]].push_back(i);
	}
	for(int i = 1; i <= n; ++i){
		cin >> f[i];
		cost[i] = 1e9 + 1;
	}
	bfs(1);
	for(int i = 3; i < level.size(); ++i){
		for(int j = 0; j < level[i].size(); ++j){
			int u = p[level[i][j]];
			u = p[u];
			u = p[u];
			u = p[u];
			if(cost[u] > abs(f[u] - f[level[i][j]])){
				cost[u] = abs(f[u] - f[level[i][j]]);
				ans[u] = level[i][j];
			}
			else if(cost[u] == abs(f[u] - f[level[i][j]])){
				ans[u] = min(ans[u], f[level[i][j]]);
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		cout << ans[i] << " ";
	}
	return 0;
}
Copy
Find a Friend Bahou
GNU G++17
178 ms
25.6 MB
Accepted