zcmimi's blog

arrow_back点分治共4篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

先钦定树的重心处理出答案

若当前点是距离最大点对的lca(即在它们之间的路径上),这个点就是最优的

否则最优答案一定在最大点对的lca的子树中

每次都选树的重心来处理,最多需要处理\log n次,总复杂度\Theta(n \log n)

avatar
zc
2020-01-05 12:24:00
查看原题

点击跳转

考虑一种颜色对答案的贡献

把树中这种颜色的点都删掉,那么就会有很多的小树,这些小树中的点互相之间不会产生贡献,而不同树的两个点之间会产生贡献。

可以得到每一种颜色,点的sum值就是n - 所在小树的size

一个点的sum就是n * 颜色数 - 每种颜色节点所在小树的size

avatar
zc
2020-01-04 20:29:00
查看原题

点击跳转

点分治

avatar
zc
2020-01-04 20:18:00
查看原题

点击跳转

点分治

1/1
Search
search