T1
是dp 设f i 0 不含k的情况书 f i 1 含k的情况数
第一步优化：前缀和 维护 f两个数组的前缀和 通过前缀转移
第二步优化：发现前缀和能矩阵乘法优化，所以矩阵快速幂就可以
说起来挺简单，式子也不算难推，但就特别难写，主要的难度在于设置矩阵上面
T2
不知怎么一直卡在35，但是打的总体上肯定是没问题的
首先注意审题，这个抽象的边条件，代表的其实是MST，所以暴力15分就来了
然后是 部分分--->正解的部分
考虑对于树的部分，采用类似于边分治的一种方法，然后用树dp维护子树上的情况数，用跨越根节点的情况更新
然后考虑图，我们怎样从图中调整出一个树呢，看条件，我们选择树边之后，一定要保证所有非树边权值大于树边，直接在分治同时维护即可
打了一晚上，还是35，日报写的比较简略
看来课件发不出来了，这就……，看看每天早上能不能提前看出来几道题吧
标签：师大附中,前缀,题解,矩阵,35,20231215,dp From： https://www.cnblogs.com/youlv/p/18076988/daily_2023ssdfzD6_2