BZOJ 2152 聪聪可可

发布于 2017-06-19  159 次阅读


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

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


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

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

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

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

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

 

 


一个非常弱的准退役OIER