跨越国度

题意:

给你一颗带边权树 及每个点的颜色 和m个操作 每次操作更改一个的颜色 求每次操作后同色最近点对的距离

题解:

点分治 对于每个重心维护x个堆 x为这个重心管辖范围内的不同颜色数

维护该重心管辖范围内这个颜色的点到该重心的距离的小根堆

则某颜色经过这个重心的最小距离就是堆的前两个点的和

答案就是所有值的最小值

修改:

对一个点修改只会影响管辖范围包括它的log(n)个重心

每个重心维护堆log(n) 所以时间复杂度为O(nlog^2(n))

修改后可能影响答案 所以总的维护一个小根堆记答案即可

(官方解题报告还多建了好几个堆和一个线段树- - 简直麻烦 理论上我这样做是对的 但是我没打orz)

原文地址:https://www.cnblogs.com/g-word/p/3614872.html