题解

可以使用 multiset来维护当节点的 {权值，深度，下标}。由于题目要求在权值之差相同时，找到离自己最近的。因为 multiset 默认是从小到大排序，这边可以将深度取相反数，这样方便维护。

具体做法如下: DFS 遍历树,对于当前节点 $u$,在 multiset 中二分找到第一个 大于等于当前节点权值 $w[u]$ 的祖先节点 $p_1$ ，并记录此时的权值差计为 $d_1$

题目描述

在小红所工作的幻想科技公司里，每位员工在需要请求权限时，必须向其直属的某位领导提出申请。为了保持决策的高效与合理，员工会选择与自己思维模式最为接近的上级领导进行沟通。公司的组织架构如同一棵树，每位员工（除了 CEO）均有一位直属上级。

每位员工的思维模式由一个唯一的正整数表示，称之为思维指数。两位员工的思维模式越接近，其思维指数的差的绝对值就越小。小红希望能够知晓，每位员工将向哪位领导提出权限请求。

输入描述

第一行包含一个正整数 $n$（$2 \le n \le 100000$），代表幻想科技的员工总数。

第二行包含 $n - 1$ 个正整数 $f_1, f_2, ..., f_{n-1}$，其中第 $i$ 个数 $f_i$ 表示编号为 $i$ 的员工的直属上级的编号 ($i < f_i \le n$)，编号为 $n$ 的员工为无上级的 CEO。

第三行包含 $n$ 个正整数 $a_1, a_2, ..., a_n$，其中第 $i$ 个数 $a_i$ 表示编号为 $i$ 的员工的思维指数。思维指数的范围在 $1$ 到 $n$ 之间。

输出描述

在一行中输出 $n - 1$ 个以空格分隔的正整数，行末不能有空格。第 $i$ 个数表示编号为 $i$ 的员工请求权限时的申请对象。若存在多个思维指数接近的上级领导，员工将选择组织架构中离自己最近的领导。

样例输入

6
3 3 5 5 6
2 5 4 1 3 6

样例输出

5 3 5 5 6

样例说明

员工 2 的直属上级是员工 3，但员工 3 的思维指数与员工 6 的思维指数都与员工 2 的思维指数 5 相差 1。由于员工 3 在组织架构中距离员工 2 更近，员工 2 会向员工 3 提出申请。

评测数据与规模

$2 \le n \le 100000$。