[POI2014]Hotel加强版

本文主要是介绍[POI2014]Hotel加强版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hotel加强版

题解

很板子的一道长链剖分。

首先应该是很容易想出它的dp方程式的。
我们令$f_{u,i}$表示在$u$的子树中，与$u$距离为$j$的点的个数，$g_{u,i}$表示在$u$的子树中，两个离它们$lca$距离与它们的$lca$与$u$距离的差值为$j$的点对个数。
显然，当我们将点$v$合并到点$u$上时，有$dp$转移式
f u , j + = f v , j − 1 , g u , j + = f u , j f v , j − 1 + g v , j + 1 f_{u,j}+=f_{v,j-1},g_{u,j}+=f_{u,j}f_{v,j-1}+g_{v,j+1} fu,j​+=fv,j−1​,gu,j​+=f

这篇关于[POI2014]Hotel加强版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---