这篇文章上次修改于 338 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
CSP2023-S模拟赛（五）赛后总结
生成树
简要题解
最小生成树依次连接 $i$ 和 $i+1$ ，最小为 $n-1$ 。
最大生成树从大到小枚举边权，然后这个边权的倍数都可以连接，因为这些点的最大公因数一定是当前枚举的边权的整倍数，一定在枚举这个边权之前枚举了，并查集判断是否已连接即可。
时间复杂度比较难说，但是很容易看到随着 $n$ 增大，时间复杂度肯定越大，经测试最大的 $n$ 能够跑过，所以没问题。
总结
考虑最小/大生成树的经典算法，是每次找剩余的边权中最大的，所以考虑从大到小枚举，同时推出正确性，其实是不难想到的。
序列
简要题解
考虑DP，式子推出后用矩阵乘法改写，然后优化。
总结
DP推出后，可从DP式本身出发，也可以考虑改写为矩阵乘法甚至是广义矩阵乘法，在发现DP状态数较多的情况下，可以考虑DP转移本身需要哪些信息，哪些信息可以合并，从而降低时间复杂度和空间时间度。
魔力
简要题解
计算移动每个点会造成的差值，会发现他们互相不影响，排序即可。
总结
对于计数问题，可以考虑每种操作对最终答案的影响，根据题目中信息将在线问题转换为离线问题。
时空结构
简要题解
访问过程中，考虑祖先节点对儿子的影响，然后将式子化简得出结论。
总结
对于每个节点可以拆开计算的问题，可以考虑分别拆开然后处理出每个值然后合并。
树上问题可以考虑拆成一条条链来处理。