这题不算难，但我想错了
当\(k = 1\)时，答案就是关键点；当\(k = 3\)时，答案就是三个节点组成路径的中间点(我想成了是一条路径)，因此对于这两种情况我们只需要输出1即可
而当\(k = 2\)时答案才是一条路径，因此我们考虑怎么计算\(k = 2\)的情况
我们反向思考，考虑对于每个点，看当他作为好点(以下设这个点为\(x\))时2个关键节点可以怎么选
我们发现答案有两种情况：
-
两个节点都在以\(x\)为根的子树里，并且他们不在同一个\(x\)的儿子的子树里
-
一个节点在以\(x\)为根的子树里，但另一个节点在\(x\)子树外
我们只需要对这两种情况分别计算贡献即可
定义\(siz_i\)表示\(x\)点第\(i\)个儿子子树大小，\(s_i\)表示\(i\)点儿子个数，则对于点\(x\)，第一种情况答案为
\[\sum_{i=1}^{s_x-1}{\sum_{j=i+1}^{s_x}{siz_i siz_j}} = \frac{(\sum_{i=1}^{s_x}{siz_i})^2-\sum_{i=1}^{s_x}{siz_i^2}}{2} \]别忘记加上第二种情况即可
最终复杂度\(O(n)\)
标签：siz,sum,子树里,答案,情况,CF1824B1,节点 From： https://www.cnblogs.com/fox-konata/p/17655984.html