🇨🇳 😗 I'm Darth Vader LOOOOOOL...🐷 🐷
模板
转化为判定某个边数是否满足条件即可，处理方式同上
动态点分治
构建点分治树，将每个点的子树按年龄排序，算出距离的前缀和
对于每个询问，从u节点开始往上讨论即可
时间复杂度$O(nlog^2n)$ ，空间复杂度$O(nlogn)$
每个点开两个堆，一个记子节点到上一层重心距离，一个记其子树到它的链,全局堆记答案
关于堆的一些操作
如果堆A是堆B[]的堆顶集合，我们修改了一个堆B[i]，怎么维护堆A？
先在堆A里删除B[i]的堆顶，操作完B[i]后，再将B[i]的堆顶加回去
void On(int x){
if(B[x].size()>1)Ans.del(B[x].getmax());
B[x].del(0);
if(B[x].size()>1)Ans.push(B[x].getmax());
for(int u=Fa[x],v=x;u;u=Fa[u],v=Fa[v]){
if(B[u].size()>1)Ans.del(B[u].getmax());
if(C[v].size())B[u].del(C[v].top()); //先删
C[v].del(Dis[x][Dep[u]]); //操作
if(C[v].size())B[u].push(C[v].top()); //操作完后加回去
if(B[u].size()>1)Ans.push(B[u].getmax());
}
}带权重心，每次从一个点开始，计算它的权值，往它最优的子节点上走（原树的)
计算权值用动态点分治，注意不与原树搞混即可
将原要求转化为Dis[i]-D[i]<=D[j]-Dis[j]
每个点开一个sbt记左边的，再开一个用作差分
给点分治树上重构即可
上静态点分治，到每个重心，二分一个答案ans
将该重心子树的边减去ans，如果找出一条权之和大于零的路径，就是满足条件的
问题变为找一条长度L,U之间的大于零的路径
枚举该重心的每一颗子树，用BFS取出当前子树的点
记下之前子树中，每种路径长度的最大值
BFS取出来的点按深度递增，于是可以用单调队列维护
优化：每个重心的子树按最大深度从小到大排序，防止被”扫把图“卡
上静态点分治，fft算一下当前答案给每个点加一下，发现每个点的子节点距离都多算了2,减掉即可
注意各种初始化
水题，dfs两遍即可。写了个搞笑的动态点分治
类似重建计划
%%% WJMZBMR... %%% VFleaking...
区间众数
分块然后排序，emmmm... 🔥
%%%Oblack...
模板 🎬
CDQ:
第一维删除时间，最先删的放在后面
第二维数组位置，小的在左边
第三位值