IOI2020国家集训队作业云做题记录

### [CF506E Mr. Kitayuta's Gift](https://www.luogu.com.cn/problem/CF506E) 最终串长度为偶数的情况下 考虑DP $f_{i,l,r}$表示最终串考虑了前后$i$个字母 给的$s$串还有中间$l$到$r$没用时的方案数 $g_i$表示最终串考虑了前后$i$个字母时给的串已经用完时的方案数 转移时根据$s_{l}$是否等于$s_r$讨论 看最终串左右两侧放哪个字母（转移一次左右各放一个相等的字母）但这个DP复杂度太高 考虑优化 发现$i$为阶段 最终其实是在一个自动机（或DAG）上走$i$步的方案数  即从abaac开始走$n$步到GOAL的方案数 但是这样自动机上点的个数是$n^2$的 考虑简化 发现点可以分为红绿两类 绿的点$s_l=s_r$ 于是可以简化路径  这样点的个数为$O(|s|)$级别 可以邻接矩阵自乘转移了 还有总长度为奇数的情况 这时从一个有两个字母的绿点无法直接结束（可以到终点再自环走一步结束） 我们考虑去掉这种直接结束的方案数 就是原图做一遍 然后只保留上述边并去掉终点自环再做一遍 方案数相减即可 ### [CF512D Fox And Travelling](https://www.luogu.com.cn/problem/CF512D) 可以发现一个边双以及多个边双之间的点永远也遍历不到 考虑缩点 每个连通块缩成一棵树 如果有环则是有根树（根遍历不到）没有环则是无根树 有根树可以DP $f_{x,i}$表示选$i$个的方案数 合并时$f_{x,i+j}=f_{x,i}\times f_{y,j}\times \binom{i+j}{j}$其实就是个EGF 无根树就每个点做一遍 求和后发现所有大小为$i$的都多算了$n-i$次 最后所有的合起来做个EGF卷积即可 ### [CF526G Spiders Evil Plan](https://www.luogu.com.cn/problem/CF526G) 首先考虑一次询问怎么做 如果$2y$比树的叶子个数多 那么所有边都可以选 否则就是选$2y$条可以到叶子的路径 考虑长链 选最长的$2y$条长链即可 我们发现每次选的一定经过直径两端之一 那么考虑随便一端 作为根 选择$2y-1$条长链就行了（因为此点一定是叶子）实现时可以把每个链搞个排名 求个前缀和之类的 如果不包括$x$ 那么找到从$x$所在长链到向上碰到（倍增跳）第一个已经选了的链的这个路径 要么把那个点所在链的后半部分替换成$x$所在路径 要么把最小的链替换成$x$所在路径 两者求max即可