点分树-动态点分治-个人总结

~~代码怎么都这么长~~ ~~还卡常~~ ## 点分树 经常用于解决待修的点分治。 具体的说，经常用于处理没有明显的子树边界的问题，比如：相距最远的两个黑点、距离一个点距离<=k的点权和...这些问题没有子树的限制，是面向整棵树的。 我们将点分治的递归结构建出来，就是点分树。很显然，这棵树的树高是$\log N$级别的，于是一些暴力的方法就可以使用了。 我们通常维护点分树上每个点的子树的信息。 ### [ZJOI2007]捉迷藏 待修改，询问相距最远的黑点的距离。 很显然，我们就是要维护每个点往下的最长链和次长链。 我们维护3个堆： h1[x]：x的子树内每个点与fa[x]的距离。 h2[x]：x的儿子的h1[v].top()。 h3：全局ans。 每次修改暴力往上跳即可。 ~~一定要区分变量名...~~ **可以用两个堆来模拟可删堆** 开灯的代码： ```cpp void ton(int p) { if(h2[p].size()>=2) h3.erase(h2[p].top()+h2[p].top2()); h2[p].erase(0); if(h2[p].size()>=2) h3.push(h2[p].top()+h2[p].top2()); for(ri x=p; fa[x]; x=fa[x]) { int f=fa[x]; if(h2[f].size()>=2) h3.erase(h2[f].top()+h2[f].top2()); h2[f].erase(h1[x].top()); h1[x].erase(dis(p,f)); if(h1[x].size()) h2[f].push(h1[x].top()); if(h2[f].size()>=2) h3.push(h2[f].top()+h2[f].top2()); } } ``` ### QtreeIV ~~懒得卡常了，只要在堆操作时，记录值是否变化，就可以少很多操作~~——还是过不去...常数太大。 由于有负边，所以答案和0取max即可。 ### 震波 修改点权，询问距离一个点<=k的点权和。 方法：对每个点开两棵动态开点线段树，一个维护距离x为i的点权和，一个维护距离fa[x]为i的点权和。查询时容斥一下，减去那个子树的贡献即可。 查询的代码： ```cpp int query(int p,int k) { int res=ask(rt[p][0],0,len,0,k); for(int x=p; fa[x]; x=fa[x]) { int f=fa[x],d=dis(p,f); if(d<=k) { res-=ask(rt[x][1],0,len,0,k-d); res+=ask(rt[f][0],0,len,0,k-d); } } return res; } ``` ### 烁烁的游戏 懒得写了，和上面刚好反过来：范围加，求单点。 ## [ZJOI2015]幻想乡战略游戏 思想和一道洛谷月赛题很想，贪心的向子树的sum*2>all的子树走，为了保证复杂度，每次走到对面子树的重心，这样只有$\log N$次，实质是借助点分树往下跳。 又是点分树的讨论：维护自己的值，和自己对父亲的贡献。 用树状数组维护子树权值和。维护$sum[x][0]$表示自己的子树到x的答案，$sum[x][1]$表示自己的子树到fa[x]的答案。 ```cpp LL calc(int p) { LL res=sum[p][0]; for(ri x=p; fa[x]; x=fa[x]) { int f=fa[x]; res+=sum[f][0]-sum[x][1]; res+=(LL)(tot[f]-tot[x])*dis(p,f); } return res; } ```