题意:
Madoka 的教室里有 nn 个座位，一开始，编号为 ii 的座位上坐着编号为 b_i(1 \le b_i \le n)bi(1≤bi≤n) 的同学。
门外有排成一队的，编号从 n+1n+1 开始的，无穷多的同学。
现在，每上一节课，坐在编号为 ii 的座位上的同学会移动到编号为 p_ipi 的座位上，所有座位的移动是同时瞬间完成的。
如果一个座位上有多个人，则只有编号最小的同学可以留在座位上，其他同学会被开除出班级。每堂课至少开除一个同学。
接着，外面的同学会依次进入教室，坐到空座位上。
在若干节课后，第 ii 个座位上坐着的同学编号为 a_iai。
给出 a,pa,p，求字典序最小的可能的 bb。
思路:
- 全排列队列,每一个点可以向外连1条线题型: 建图
- 可以得到一个 深林图, 每一个树有一个环,环外点的方向一定指向环. (当然也可以只是一个环 (每一个点都被其他一个点所指向))
- 就是一个树 多了一个边而已. n个边
- 这道题就是一个 树+环,
- 然后找规律,发现新进来的点一定会被其他点给挤出去(他的编号比其他点大), 每一次新点冲入度为0的点进去
- 由此可以得到轮数
- 轮数得到,就可以知道 最初的图上的点 经过n论后 会在图上的那个位置, 这里利用倍增法处理
- 由此可知 现在图上 id <=n 的点 会和哪些位置的点进行比较,
- 现在问题就转化成了, 将这些已知点和未知点 放在图上使得字典序最小,
- 首先, 贪心得将已知点放在他所占据位置的下标最靠前的位置, 因为他 一定比这些位置上的点小,才符合题意
- 接下来就是放未知点, 由小到大得放未知点, 放在能翻的位置的下标最靠前的, 先放完已知点,在放未知点是不好处理的
- 于是 将所有的点 由大到小放, 已知点就如上所说, 未知点就放在之前已知点所带来的位置下标最小的位置, (因为他一定比之前的点大), 这里用map处理即可
标签：Madoka,一个点,Sixth,位置,图上,二叉树,编号,未知,座位 From： https://www.cnblogs.com/Lamboofhome/p/16818080.html