时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
题目描述
Goodbye and farewell. Good and well.
A rooted tree of nodes is given. Each node
has a colour
.
Furthermore, there is a glittering diamond embedded in each node . Its colour
is an arbitrarily chosen integer, and it lights up all nodes in the subtree of
whose colour equals
. Let
be the number of nodes lit up by the diamond on node
, and this diamond gets a shininess value of
.
You are to choose the colours of each diamond, and maximize the mex function of — that is, the smallest non-negative integer not appearing in — the set of shininess values of all diamonds.
输入描述:
The first line contains an integer n () — the number of nodes.
The second line contains n - 1 space-separated integers(
) — the parents of nodes 2 through n, respectively. The input guarantees that these values describe a connected rooted tree with node 1 being the root.
The third line contains n space-separated integers(
) — the colours of nodes 1 through n, respectively.
输出描述:
Output one integer — the largest possible mex of the set of shininess values.
示例1
说明
An optimal choice of diamonds' colours are: 2, 2, 5, 3, 2, 1, 0, 0, for diamonds on nodes 1 through 8 respectively. Note thatcan be an arbitrary integer and not limited to colours that appear on the tree.
The respective shininess values are 6, 4, 5, 3, 2, 1, 0, 0. The mex of this set is 7.
备注:
Please be aware that the memory limit of this problem is unusual. Your solution may not be an intended one if it appears to require too much memory.