边分治、二度化
边分治、二度化
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266447
边分治可以使每次分治时恰好只有两边的点，统计贡献起来非常方便
但是朴素边分治时不行的，菊花图可以卡掉，所以要把点二度化，以这个图为例：
二度化后为：
再举个例子：
二度化后是：
绿点是原图点
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-28
边分治+虚树+直径合并：P4220通道
边分治+虚树+直径合并：P4220通道 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266426 https://www.luogu.com.cn/problem/P4220 第一棵树可以直接边分治，然后黑白染色，弄到第二棵树上建虚树 第三棵树很难搞。需要回到题目本身，发现题目没叫我们求奇奇怪怪的东西，而是求距离，肯定有啥性质，而且还是最大距离，就是一个点集的直径。 直径显然支持合并性，我们直接在虚树上树形dp进行合并即可 123456pre cod...
2023-12-28
边分治建虚树优化：P4565暴力写挂
边分治建虚树优化：P4565暴力写挂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135272909 https://www.luogu.com.cn/problem/P4565 首先题目的式子很难看，可以变成 ： depx+depy+dis(x,y)−deplca2(x,y)2\frac {dep_x+dep_y+dis(x,y)-dep_{lca_2(x,y)}}2 2depx+depy+dis(x,y)−deplca2(x,y) 然后直接边...