[AGC记录] AGC005题解

我觉得这一场非常神啊。
A, B题还是简单题为什么单调栈板子有400分啊
C的条件看起来有点像某个集训队作业题, 注意到直径的性质以后就很简单了。这tm有900?
D是经典容斥题 ~K Perm Counting
做法是先把限制容斥成至少的情况, 然后把限制建图, 在链上dp或者用组合数搞搞即可。

E

E比较有意思, 但是发现两个性质以后也比较简单。
我们让第一棵树以(x)为根, 第二棵树以(y)为根, 那么第一个人可以走到这个点的前提是路径上所有点(u)满足(depa_u < depb_u)。还有一个性质是如果第一个人走到一个点, 这个点和连出的一条边连向的点在第二棵树上的距离大于(2), 第一个人就无敌了。所以我们的策略就是判断第一个人可以到的所有点里面能不能无敌, 不能无敌就找可以到的(B)里面最深的点挂机就好了。

F

F貌似刚学NTT的时候做到了。然后现在再看啥也不会
首先可以把问题转化成考虑一个点(x)(ans_i)的贡献, 考虑一个(x)在多少情况下不在点集内, 那么要么是全在(x)的儿子的一个子树里面, 要么是全不在(x)的子树里面。
那么对贡献求和就是答案了。
暴力算是(n^2)的, 但是可以发现枚举儿子的部分换成“有多少子树大小为(i)的点”这一条件以后可以让式子变成卷积, NTT即可。

原文地址:https://www.cnblogs.com/clover4/p/15363512.html