bzoj3068:小白树

双带权重心&＃xff1f;

枚举分解点x&＃xff0c;x子树内找到一个&＃xff0c;x子树外找到一个

考虑一般的操作是贪心移动&＃xff0c;与子树总权值有关系

所以不妨按照子树权值进行树链剖分

那么一个点子树内的重心一定在重链上。

从重儿子贪心往上走即可

子树外&＃xff1f;

设子树外所有点权值总和是c

先倍增二分找到第一个扣除x的子树总权值之后权值>c/2的

再从这个子树的重链往下走&＃xff0c;找到第一个子树权值>c/2的。用线段树二分实现

但是bzoj卡空间&＃xff0c;然后咕了。

代码.cpp

找重心&＃xff1a;贪心移动&＃xff0c;权值树剖&＃xff01;

双信息&＃xff1a;枚举分割点