某地主担心农民偷取他的粮食，雇人挖了大量地窖来屯粮，这些地窖层层排列，只有一个总入口。 每个地窖都有一个随机且唯一的数字编号(1 ... N)。聪明的农夫经过一番侦察，发现所有的地窖形成了一颗满二叉树，只有叶子节点中才存放有粮食，粮食数量与地窖编号相同。 狡猾的地主设置了报警装置，只要任意两个相邻的叶子节点中粮食被偷，就会自动报警。
农夫事先并不知道地窖分布图，但是他无意间得到了地窖组成的二叉树的前序遍历和中序遍历结果，请帮忙计算一下，在不触发报警装置的情况下，农夫最多可以偷取地主多少粮食。
提示：
第一行输入一个数字n表示有n个节点的满二叉树
第二行n个数字a[0],a[1]...a[n-1]用空格隔开，表示二叉树的前序遍历
第三行n个数字b[0],b[1]...b[n-1]用空格隔开，表示二叉树的中序遍历
数据范围：
3<=n<=105 且n可以表示成2k-1（k为整数）
a[0]...a[n-1]中1,2...n每个数字分别出现一次
b[0]...b[n-1]中1,2...n每个数字分别出现一次
输出一个数字，表示农夫最多可以偷取地主多少粮食
3 2 1 3 1 2 3
3
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
