POJ1987 Distance Statistics 【树分治】

By | 2016-08-13

比较简单的树分治:给一棵树,边权代表两点间长度。求有多少对点,他们之间长度不大于K。

  • dis[x] + dis[y] <= k
  • dis[x] <= k - dis[y]

以k - dis[y]组成的数组,二分查找小于 dis[x] 的个数cnt, 则贡献 n - cnt - 1(自己不纳入计算)

再去掉子树重复计算的部分即可。见代码

 

发表评论

电子邮件地址不会被公开。