洛谷 P6668 - [清华集训2016] 连通子树（虚树+点分治）

本文主要是介绍洛谷 P6668 - [清华集训2016] 连通子树（虚树+点分治），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷题面传送门

一道思维难度为 \(<\epsilon\) 的题。

首先先考虑单组询问的情况。有个究极暴力的做法，\(dp_{i,x,y,z}\) 表示 \(i\) 子树内三种颜色个数分别为 \(x,y,z\) 的连通块个数，转移相当于合并两个连通块，只能 \(O((na+1)^2(nb+1)^2(nc+1)^2)\) 地进行，因此单组询问复杂度 \(n(na+1)^2(nb+1)^2(nc+1)^2\)，太逊了。

考虑优化这个暴力，一个切入点是上面的 DP 中合并复杂度很大，而如果我们假定根节点选择了，我们就可以采用【DFS 一个节点时，将父亲的 DP 值传给儿子，回溯时将儿子的 DP 值加到父亲上】的套路，这样就只涉及插入一个点，可以 \(O(1)\) 转移。而这样的 DP 一般只能与点分治相结合，具体方法就是点分治一个连通块时，考虑求出分治重心必选的方案数，这部分就套用上面的做法即可，时间复杂度 \(n\log n(na+1)(nb+1)(nc+1)\)，但是有多组询问，同样不行。

到这里我们还没有用到每种颜色出现次数 \(\le 5\) 的性质。考虑如何应用之，另一个粗暴的想法是容斥，具体来说你先强制一些 \(a,b,c\) 必须选，然后二项式反演把它容斥掉，怎样求包含一个点集的连通块个数呢？首先建出这些点集的虚树，然后预处理出 \(dp_i\) 表示由 \(i\) 子树内组成的包含 \(i\) 的连通块个数，\(dpout_i\) 表示由 \(i\) 子树外的点组成的包含 \(fa_i\) 的连通块个数。那么这个方案数就直接将虚树周围的 \(dp_i+1\) 或者 \(dpout_i+1\) 乘起来即可。这样单组询问时间复杂度大概是 \(32^3·15·\log n\)，还是不行。

考虑将二者结合在一起，建出三种颜色的 \(5\) 个点共 \(15\) 个点的虚树，然后在虚树上点分治即可。在建虚树的时候，我们要对于一条链 \(x,y\)，求出有多少个 \(x\to y\) 的点及其子树内的点组成的连通块包含 \(x\) 不包含 \(y\)，或者包含 \(y\) 不包含 \(x\)，或者既包含 \(x\) 又包含 \(y\)，这部分可以线段树/倍增预处理出来。时间复杂度 \(15(n+q)\log n+\sum abc·\log\sum abc\)。

然而看看就不想写（

这篇关于洛谷 P6668 - [清华集训2016] 连通子树（虚树+点分治）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！