{"problem":{"name":"[PA 2020] Bardzo skomplikowany test","description":{"content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Bardzo skomplikowany test](https://sio2.mimuw.edu.pl/c/pa-2020-1/bst/)** Bytie 刚刚参加了算法和数据结构这门课的面试。他没有为之学习太长时间，所以他做得不是太好。经过几","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9103"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Bardzo skomplikowany test](https://sio2.mimuw.edu.pl/c/pa-2020-1/bst/)**\n\nBytie 刚刚参加了算法和数据结构这门课的面试。他没有为之学习太长时间，所以他做得不是太好。经过几分钟的交谈，这位心碎的主讲老师决定给这个男孩最后一次机会。\n\n- 「孩儿，你知道啥是 BST 不？」教授问\n\nBytie 听到这句话后内心狂喜，因为在他上课睡觉的时候记住了一些理论。\n\n- 「知道。大小为 $n$ 的 BST 是一棵有根树，其顶点用 $1$ 到 $n$ 的整数来编号。每个节点最多可以有两个子节点；它可以有一个最多一个左子节点和一个最多一个右子节点。此外，每个节点的编号必须大于其左子树中所有节点的编号，并小于其右子树中所有顶点的编号。」Bytie 回答说，他达到了他潜意识的深处。\n- 「很好。让我们看看你是否记住了如何对 BST 进行旋转。」一直坐在那里的教授回答说。他站起来，向黑板走去。\n\nBytie 被冷汗浸透了。他一时失去了信心，因为他记不起旋转的具体原理（可能在上这节课的时候，他正在另一边摸鱼，没听课）。考官在黑板上画了两棵同样大小的 BST 树，并让 Bytie 用正确的旋转将第一棵树转化为第二棵树。\n\nBytie 想了一会儿，认为左旋就是选择某个节点 $v$ 和它的右子节点 $w$，并让 $w$ 成为 $v$ 的父节点。Bytie 的直觉用以下伪代码描述。\n\n```\nif v.Parent != null then\n    if v.Parent.RightSon == v then\n        v.Parent.RightSon := w\n    else\n        v.Parent.LeftSon := w\nw.Parent := v.Parent\nv.Parent := w\nw.LeftSon := v\nv.RightSon := null\n```\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/shqgiur7.png)\n\n以此类推，Bytie 理解了右旋，其中 $w$ 是 $v$ 的左子节点。\n\n```\nif v.Parent != null then\n    if v.Parent.RightSon == v then\n        v.Parent.RightSon := w\n    else\n        v.Parent.LeftSon := w\nw.Parent := v.Parent\nv.Parent := w\nw.RightSon := v\nv.LeftSon := null\n```\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/tpmzihlx.png)\n\n然而，Bytie 很快就注意到有些不对劲。如果节点 $w$ 在左旋时有左子树，它就会丢失！同样在右转过程中，节点 $w$ 的右子树也会丢失。\n\n- 「快点孩儿，你不是唯一一个想通过这次考试的人。」教授不耐烦地催促道。\n\n在没有太多时间考虑的情况下，Bytie 假设只有在这个有问题的子树是空的情况下才能执行旋转，也就是说，如果没有顶点丢失并且树保持一致的话才进行旋转。\n\n为了尽快结束他的煎熬，他决定进行最少次数的旋转，使他能够将第一棵树变成第二棵。请告诉他这是否可行，如果可行，他需要进行多少次轮换？由于这个数字可能相当大，请告诉他这个值对 $10^9+7$ 取模后的值。\n\n## Input\n\n第一行包含一个整数 $n$，表示这个 BST 的大小。\n\n接下来两行描述这两棵树。对于一棵树用一行 $n$ 个整数 $a_1,a_2,\\cdots,a_n$ 描述。如果 $a_i\\ge 1$，表示 $i$ 节点的父节点；如果 $a_i=-1$，则表示这是树的根节点。\n\n你可以假设这两棵树都是合法的 BST，即树中没有环，恰好有一个根节点，每个节点最多只有一个比自己小的子节点和一个比自己大的子节点。\n\n## Output\n\n输出应该包含一个整数，表示用 Bytie 的方式把第一棵树转化为第二棵树所需最少旋转次数对 $10^9+7$ 取模后的值，如果不可能转化，输出 $-1$。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n下图展示了旋转最小次数所采取的旋转方式。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/f1dblwez.png)\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\le 5\\times 10^5$，$-1\\le a_i\\le n$，$a_i\\neq 0$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9103","tags":["贪心","2020","笛卡尔树","PA（波兰）"],"sample_group":[["4\n3 1 -1 3\n2 -1 4 2","3"],["8\n2 4 2 7 4 5 -1 7\n2 3 6 5 3 -1 6 7","7"]],"created_at":"2026-03-03 11:09:25"}}