这是DSA 2023 Spring PA 2的Build的解题报告，内容涉及使用二叉树实现多叉树和后序遍历。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
二叉树：以邻接表形式输入的数据被转化成二叉树，以便于后续访问和处理。
栈：为了初始化树中各节点的高度和子树规模，使用了略有改进的后序遍历。为了避免递归，使用了栈。
算法构思：
1、输入数据，在输入的时候进行处理，转化成二叉树
2、使用略有改进的后序遍历（弟弟->兄长->父亲，而不是兄长->弟弟->父亲），初始化每个节点的高度和子树规模。
3、接收操作，每个操作立刻执行。具体来说：对于子树移动操作，先找到源子树，将源子树移除，修改原来位置以上各节点的子树规模和高度。再找到目的位置，将源子树接入，修改源子树节点以上各节点的子树规模和高度。对于查询操作，直接找到位置输出即可。
4、为了确保3中的复杂度和cost成线性关系，储存并维护每个节点的所有弟弟节点的高度最大值、子树规模之和。这样更新数据时只需要沿着找到这个点的路径回溯更新即可，不再需要遍历该点的所有弟弟节点。
实现要点：
1、使用定长的结构体数组存放树的信息，每个点的信息由一个结构体对象承载。
2、使用二叉树避免使用指针造成的空间管理困难。
3、移动操作中接收插入位置rank后，如果rank>0，必须将rank减1，这样来寻找插入位置的兄长，以确保能够找到。
4、更新树的结构时，注意更新顺序，确保后面会用的信息不要先更新。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题1：除了前4个测试点外全部超时，而且运行时间超过2秒。
考虑到已经确保复杂度不会超过cost的线性，因此考虑是死循环造成的。由于源程序中没有什么while会造成死循环，所以检查树的更新是否有问题。最终发现是摘除源子树时没有断开源子树和其弟弟的联系。
问题2：除了前4个测试点大面积wrong answer。
考虑到大量的测试点同时出现bug，还是很可能在树的更新过程中出现问题。经过检查，发现是在移动操作插入源子树后，从其父节点而不是自身开始更新信息导致错误。如果其自身储存的所有弟弟节点的高度和子树规模需要更新的话，就会因为实际上没有更新而出现错误。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
这道题最主要的耗时是在执行操作环节，其他环节可忽略。
确保每一次移动和查询操作自身复杂度为O(1)，找到对应操作节点的过程复杂度与cost成线性关系。
空间复杂度
由于使用的是定长结构体数组，所以开辟的空间是常数值。
实际使用的空间大小与节点个数成线性关系，O(n)。