5.8考试

# 考试总结 #### [$blog$](https://www.cnblogs.com/Varuxn/p/14768953.html)食用效果更佳 ## [$T1$ 树](https://www.luogu.com.cn/problem/U161904) 最关键的一个点在于$2$的爸爸只能是$1$， 因此，可以把一棵树分为两部分： * 以$2$为根节点 * 除去$2$及其子树还有$1$节点的那一部分 然后就可以在这两棵树之间愉快的反复横跳了$QAQ$ * 以 2 为根的子树中最深节点的深度比其它部分的要小 首先，这个其它部分一定要存在，至少有一个节点，再减去 1这个节点，以 $2$ 为根的子树（太麻烦了，直接称作树 $A$ ，其它部分称作树 $B$ ）大小 $k$一定小于等于$i-2$ 而为了保持它的最深子节点深度比树$B$的深度小，深度 $l$要小于等于 $j-2$ 这样，这棵树的结构数就有两边乘起来这么多。 而两边的结构数已经算好了。 还有一点：我们要枚举两棵子树中的节点各是哪些，所以要乘上一个组合数 *上一层的组合数仅仅只枚举各子树中的结构，不影响当前层 * 以$2$为根的子树中最深节点的深度比其它部分的要大或者两者相等 这时，树 A 的最大大小便是 $i-1$了，而且它的最深子节点深度一定是 $j-1$ 所以我们枚举树 B 的深度，再进行一个枚举 最后再除以一个$(i-1)!$ 转载自[$blog$](https://blog.csdn.net/qq_39973668/article/details/102963317) ## [$T2$信号传递](https://www.luogu.com.cn/problem/P6622) 整了挺长时间的，那天晚上回宿舍又想了大约一个小时才差不多。。。 ### [题解](https://www.cnblogs.com/Varuxn/p/14754851.html) ## [$T3$树](https://www.luogu.com.cn/problem/P6623) 感觉这个题比第二个题通俗易懂多了, 我果然变聪明了 ~~(大概是别人题解写的比较好吧。。)~~ 有两种做法吧 * ### 状压 可以观察到对于每个数倒数第n位有一个长度为$2^k$的$0$和$1$交替的循环节，这也是解决问题的根本所在。 然后就是用树上差分，再对于不同的深度状压一下就好了 * ### 线段树合并 具体作法参考[$blog$](https://www.luogu.com.cn/blog/zxB/heoi2020-shu)