BZOJ 2152 聪聪可可


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2152

题意:求出树上两点间距%3=0 的有序点对个数...


大概是点分治最简单的例题了.... 然而蒟蒻博主想了很久...

找这样的点对是不容易的,我们考虑将问题转化为求树上长度%3=0 的路径数,显然这是等价的

点分治的核心思路在于分治,即:求出经过当前根节点的合法路径——> 删除根节点,递归每个子树。

对于此题,当我们确定根节点时,这颗树内的合法点对数即 (深度%3=0 的点数)^2+(深度%3=1 的点数)*(深度%3=2 的点数)*2... 这是显然的

每次递归的时候需要去除掉没有经过根节点的答案....

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2152 聪聪可可


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,