Preface
随机跳题做到了这道。
题目
https://www.luogu.com.cn/problem/P2899
题解
其实就是交叉染色。我们考虑每棵子树的情况。设
: 自己本身被染色 : 的某个儿子染色了,使之被覆盖进了范围 : 的父亲染色了,使之被覆盖进了范围
接下来是转移方程:
我们会发现如果上暴力的话,第二个转移方程的复杂度是
化简一下:
这个复杂度是
随机跳题做到了这道。
https://www.luogu.com.cn/problem/P2899
其实就是交叉染色。我们考虑每棵子树的情况。设
接下来是转移方程:
我们会发现如果上暴力的话,第二个转移方程的复杂度是
化简一下:
这个复杂度是
随机跳题做到了这道。
https://www.luogu.com.cn/problem/P2899
其实就是交叉染色。我们考虑每棵子树的情况。设
接下来是转移方程:
我们会发现如果上暴力的话,第二个转移方程的复杂度是
化简一下:
这个复杂度是