BZPRO
#4791. [CERC2016]Free Figurines
内存限制：512 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
俄罗斯套娃是一些尺寸递增的木制雕像，它们可以嵌套在一起。每个套娃可以放进一个更大的套娃，也可以被放入
一个更小的套娃。每个套娃内部最多只能直接嵌套一个套娃，但是那个套娃内部还可以继续嵌套。给定n个尺寸互
不相同的套娃，按尺寸从小到大依次编号为1到n。如果套娃a被直接嵌入套娃b，那么我们称b是a的父亲，如果一个
套娃没有父亲，那么我们称它是自由的。一组镶嵌方案可以用每个套娃的父亲来表示。我们可以每步可以做以下两
种操作中的任意一种：
1.把一个自由的套娃直接嵌入一个更大的没有被放入东西的套娃。
2.选择一个不自由的套娃，将其从其父亲中取出。
给定初始局面，请计算达到目标局面的最小的操作步数。
输入格式
第一行包含一个正整数n(1<=n<=100000)，表示套娃的个数。
第二行包含n个整数p_1,p_2,...,p_n(0<=p_i<=n)，依次表示初始局面中每个套娃的父亲，0表示自由套娃。
第三行包含n个整数q_1,q_2,...,q_n(0<=q_i<=n)，依次表示目标局面中每个套娃的父亲，0表示自由套娃。
输入数据保证初始局面和目标局面均合法。
输出格式
输出一行一个整数，即最小操作步数。
样例
样例输入
7
3 5 4 0 7 0 0
3 5 0 6 7 0 0
样例输出
2
数据范围与提示
BZPRO