首页 > 分享 > P3920 紫荆花之恋

P3920 紫荆花之恋

花匠小妙招
2024-12-11 18:22

发现题解区的大佬们讲解重构点分树部分蒟蒻不是很能理解，当时就是卡在了如何重构部分，于是来写一篇题解。

题意大概就是给出一棵支持插入点的树，每个点有和自己父亲的距离 w_i 和自己的探索半径 r_i，问每次插入一个新的点之后有多少对点满足 r_i+r_jgeq dis(i,j)。

首先我们可以记录一个答案变量，每次加入新点时统计这个新点的贡献就可以了。由于答案和树的形态无关，所以可以考虑建造点分树。

那么我们一步一步来：

统计贡献

我们设 d_i 表示 i 点到点分树上某个父亲节点的距离，那么上面的式子就变成了 r_i+r_jgeq d_i+d_j ，移个项就变成了 r_i-d_igeq d_j-r_j，所以可以在点分树每个点上用平衡树维护子树内的 d_i-r_i,如果要累加答案就在点分树上暴力跳父亲，统计满足 d_j-r_jleq r_i-d_i 的 j 的个数即可。然后更新父亲信息，暴力跳父亲把自己的 d_i-r_i 插到父亲的平衡树里面。

为了避免一个子树内在父亲处的互相配对，我们对每个点再另外开一棵平衡树维护自己子树对父亲的贡献，统计答案时再减去即可。于是我们维护了两颗替罪羊树，把上面那个叫做 1 号，这个叫做 2 号树。

另外考虑如何计算 d_i，我们发现倍增可以很好的实现这个操作，于是加入一个点的时候处理一下它的倍增数组就行了。

重构点分树

我们在插入一个点的时候在点分树上也是直接把它插到原树父亲上面，所以这样会导致点分树在插入一些点之后可能会出现不平衡的情况，评判标准是某个子树的大小超过了自己的总的子树的大小乘上一个值 alpha。

这样的话就需要我们去重构点分树。重构点分树在原树上的表现是重构一个连通块，但是在点分树上的表现就是重构一个子树，所以我们发现一个点在点分树上面的子树不平衡时，直接遍历一遍它在点分树上面的子树，然后重新找这个点分树上的重心，重新连边建树即可。

再具体一点就是，我们把子树内的所有点遍历一边(bfs,dfs 都可以)，然后把当前点的平衡树所有节点清空回收，重新计算一遍它的子树大小，然后重建的时候再次暴力跳父亲，把自己的所有信息重新插到父亲节点的平衡树里，但是注意这里就不是一直跳父亲跳到头了，而是只跳到被重构的最浅的那个父亲为止，因为再上面的父亲肯定已经包含过自己的信息，而且子树重构不会改变对这些父亲的影响（因为反正都是从被重构的这个子树跳过来的，怎么跳过来无所谓）。

这样的话，我们就可以一边重建子树，一边把信息传递给父亲，让点分树重新平衡下来。

然后这里的平衡树我用的是替罪羊树，由于重构点分树代价比较大，可以把替罪羊树和点分树的 alpha 都设成 0.8。

有道重构点分树的题可以练练手： link

一些小细节

我们发现重构点分树和替罪羊树时如果自己子树不平衡，自己的父亲子树也不平衡时直接重构自己父亲的子树就可以了，因为如果重构自己子树，自己的父亲还是会不平衡，所以还不如直接重构父亲，这样也可以让自己平衡。这样的话我们每次如果要重构就找到最上面的不平衡的父亲重构即可。重构点分树时，清空替罪羊树的节点后可以回收到内存池中，重复利用，这样可以避免内存爆炸。由于 1 号节点处理答案时有一些奇奇怪怪的问题所以可以拿出来单独判断处理。边权很大所以要开 long long。在清空子树时一定要判一下当前节点不是 0 再扔到内存池里面，否则会把 0 扔进去，然后一个节点 pushup 的时候就会把0的信息统计进去，然后就会炸裂，别问我怎么知道的

然后就没了。放一下代码：

#include<cstring> #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> namespace EMT{ typedef long long ll;typedef double db; #define pf printf #define F(i,a,b) for(int i=a;i<=b;i++) #define D(i,a,b) for(int i=a;i>=b;i--) inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;} inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);} inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;} inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");} const int N=1e5+10,mod=1e9;const db alp=0.8; int head[N],co,n,r[N];struct node{int next,to,w;}e[N<<1]; ll ans; namespace times{ int f[N][20],log[N],deep[N];ll pre[N]; inline void init(){ log[0]=-1; F(i,1,n)log[i]=log[i>>1]+1; } inline void add(int next,int to,int w){ e[++co]={head[next],to,w},head[next]=co; e[++co]={head[to],next,w},head[to]=co; int x=next,y=to;f[y][0]=x,deep[y]=deep[x]+1;pre[y]=pre[x]+w; F(i,1,log[deep[y]])f[y][i]=f[f[y][i-1]][i-1]; } inline int getlca(int a,int b){ if(deep[a]<deep[b])a^=b^=a^=b; D(i,log[deep[a]-deep[b]],0)if((1<<i)<=deep[a]-deep[b])a=f[a][i]; if(a==b)return a; D(i,log[deep[a]],0)if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i]; return f[a][0]; } inline ll getdis(int x,int y){return pre[x]+pre[y]-pre[getlca(x,y)]*2;} } namespace sgt{ int rt[N],tot,ls[N*60],rs[N*60],s[N*60],top,rec[N]; struct dp{ll val;int psiz,rsiz,cnt;}t[N*60]; inline int New(){if(top)return s[top--];return ++tot;} inline void pia(int p){ if(!p)return; if(ls[p])pia(ls[p]); rec[++rec[0]]=p; if(rs[p])pia(rs[p]); } inline void clear(int &p){ if(!p)return; if(ls[p])clear(ls[p]); if(rs[p])clear(rs[p]); s[++top]=p;t[p].cnt=t[p].rsiz=t[p].psiz=0; p=0; } inline void up(int p){ if(!p)return; t[p].psiz=t[ls[p]].psiz+t[rs[p]].psiz+1; t[p].rsiz=t[ls[p]].rsiz+t[rs[p]].rsiz+t[p].cnt; } inline int rebuild(int l,int r){ if(l>r)return 0; int mid=(l+r)>>1,p=rec[mid]; ls[p]=rebuild(l,mid-1),rs[p]=rebuild(mid+1,r); up(p);return p; } inline bool check(int &p){ if(t[p].psiz*alp<max(t[ls[p]].psiz,t[rs[p]].psiz)){ rec[0]=0,pia(p),p=rebuild(1,rec[0]);return 1; }return 0; } inline void ins(int &p,ll v){ if(!p){p=New(),t[p].psiz=t[p].rsiz=t[p].cnt=1,t[p].val=v,ls[p]=rs[p]=0;up(p);return;} if(t[p].val==v){t[p].cnt++;up(p);return;} if(t[p].val<v)ins(rs[p],v);else ins(ls[p],v);up(p); return; } inline void dfs(int &p,ll v){ if(!p)return; if(check(p))return; if(t[p].val==v)return; if(t[p].val<v)dfs(rs[p],v); else dfs(ls[p],v); } inline int ask(int p,ll v){ if(!p)return 0; if(t[p].val==v)return t[p].cnt+t[ls[p]].rsiz; if(t[p].val>v)return ask(ls[p],v); return ask(rs[p],v)+t[p].cnt+t[ls[p]].rsiz; } inline void insert(int &p,ll v){ins(p,v),dfs(p,v);} } namespace sgt2{ int rt[N],tot,ls[N*60],rs[N*60],s[N*60],top,rec[N]; struct dp{ll val;int psiz,rsiz,cnt;}t[N*60]; inline int New(){if(top)return s[top--];return ++tot;} inline void pia(int p){ if(!p)return; if(ls[p])pia(ls[p]); rec[++rec[0]]=p; if(rs[p])pia(rs[p]); } inline void clear(int &p){ if(!p)return; if(ls[p])clear(ls[p]); if(rs[p])clear(rs[p]); s[++top]=p;t[p].cnt=t[p].rsiz=t[p].psiz=0; p=0; } inline void up(int p){ if(!p)return; t[p].psiz=t[ls[p]].psiz+t[rs[p]].psiz+1; t[p].rsiz=t[ls[p]].rsiz+t[rs[p]].rsiz+t[p].cnt; } inline int rebuild(int l,int r){ if(l>r)return 0; int mid=(l+r)>>1,p=rec[mid]; ls[p]=rebuild(l,mid-1),rs[p]=rebuild(mid+1,r); up(p);return p; } inline bool check(int &p){ if(t[p].psiz*alp<max(t[ls[p]].psiz,t[rs[p]].psiz)){ rec[0]=0,pia(p),p=rebuild(1,rec[0]);return 1; }return 0; } inline void ins(int &p,ll v){ if(!p){p=New(),t[p].psiz=t[p].rsiz=t[p].cnt=1,t[p].val=v,ls[p]=rs[p]=0;up(p);return;} if(t[p].val==v){t[p].cnt++;up(p);return;} if(t[p].val<v)ins(rs[p],v);else ins(ls[p],v);up(p); } inline void dfs(int &p,ll v){ if(!p)return; if(check(p))return; if(t[p].val==v)return; if(t[p].val<v)dfs(rs[p],v); else dfs(ls[p],v); } inline int ask(int p,ll v){ if(!p)return 0; if(t[p].val==v)return t[p].cnt+t[ls[p]].rsiz; if(t[p].val>v)return ask(ls[p],v); return ask(rs[p],v)+t[p].cnt+t[ls[p]].rsiz; } inline void insert(int &p,ll v){ins(p,v),dfs(p,v);} } namespace tree{ int fa[N],siz[N],maxn,mx[N],rt,deep[N];bool vis[N]; inline void getans(int x){ if(times::pre[x]<=r[x]+r[1])ans++; for(int i=fa[x];i;i=fa[i])ans+=sgt::ask(sgt::rt[i],r[x]-times::getdis(x,i)); for(int i=fa[x];fa[i];i=fa[i])ans-=sgt2::ask(sgt2::rt[i],r[x]-times::getdis(x,fa[i])); } inline void add(int x){ for(int i=x;i;i=fa[i])sgt::insert(sgt::rt[i],times::getdis(x,i)-r[x]),siz[i]++; for(int i=x;fa[i];i=fa[i])sgt2::insert(sgt2::rt[i],times::getdis(x,fa[i])-r[x]); } inline void clear(int k,int f,int lim){ siz[k]=mx[k]=fa[k]=deep[k]=vis[k]=0; sgt::clear(sgt::rt[k]),sgt2::clear(sgt2::rt[k]); for(int i=head[k],j;i;i=e[i].next)if((j=e[i].to)!=f){ if(deep[j]<lim)continue; clear(j,k,lim); } } inline void findrt(int x,int fa){ siz[x]=1,mx[x]=0; for(int i=head[x],j;i;i=e[i].next)if(!vis[j=e[i].to]&&j!=fa){ findrt(j,x),siz[x]+=siz[j],mx[x]=max(mx[x],siz[j]); }mx[x]=max(mx[x],maxn-siz[x]); if(mx[x]<mx[rt])rt=x; } inline void dfs(int x,int lim){ vis[x]=1; if(x!=1){ for(int i=x;i;i=fa[i])if(deep[i]>=lim) sgt::insert(sgt::rt[i],times::getdis(i,x)-r[x]);else break; for(int i=x;fa[i];i=fa[i])if(deep[i]>=lim) sgt2::insert(sgt2::rt[i],times::getdis(fa[i],x)-r[x]);else break; } int st=maxn; for(int i=head[x],j;i;i=e[i].next)if(!vis[j=e[i].to]){ maxn=siz[j]<siz[x]?siz[j]:st-siz[x]; mx[rt=0]=n+1,findrt(j,x); fa[rt]=x,deep[rt]=deep[x]+1,siz[rt]=siz[j]; dfs(rt,lim); } } inline void rebuild(int x){ maxn=siz[x],mx[rt=0]=n+1; int dep=deep[x],f=fa[x]; clear(x,0,dep); findrt(x,0); fa[rt]=f,deep[rt]=dep,siz[rt]=maxn; dfs(rt,dep); } inline void judge(int x){ int goal=0; while(fa[x]){ if(siz[fa[x]]*alp<=siz[x])goal=fa[x]; x=fa[x]; }if(goal)rebuild(goal); } inline void upd(int x){ add(x),judge(x); } } inline short main(){ read();n=read();times::init(); read(),read();r[1]=read(); tree::vis[1]=1,tree::siz[1]=1;pi(0);pn(); F(i,2,n){ int f=read()^(ans%mod),w=read();r[i]=read(); times::add(f,i,w),tree::fa[i]=f; tree::deep[i]=tree::deep[f]+1; tree::vis[i]=1; tree::getans(i),tree::upd(i); pi(ans);pn(); } return 0; } } signed main(){return EMT::main();}