首页 > 分享 > 题解洛谷 P3920 【[WC2014]紫荆花之恋】

题解洛谷 P3920 【[WC2014]紫荆花之恋】

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

对于本题这样带修的树上路径问题，考虑用动态点分治来解决。

将题目中给的式子变形得：

valx+valy⩾disx,yvaly⩾disx,y−valx" role="presentation">valx+valy⩾disx,yvaly⩾disx,y−valx

对于点分树上的每个节点 x" role="presentation">x 维护 disx,y−valx" role="presentation">disx,y−valx，y" role="presentation">y 为在点分树上其子树内的节点。查询时只需考虑对于当前子树，维护的权值小于等于插入的节点权值的个数。

考虑到时空限制，点分树上每个节点用平衡树来维护信息，并且还需使用快速的 Treap" role="presentation">Treap 或者替罪羊树。在点分树上向上跳时，查询其在点分树上的祖先时，为了避免算重，还需减去其子节点对应连通块的贡献，这里对每个节点再维护一个平衡树即可。

在不断插入节点后，点分树会越来越不平衡，可以应用替罪羊树的思想，当一个节点子树大小和其父亲节点子树大小满足不平衡的判定关系后，就对该子树进行重构，对节点上维护的平衡树进行垃圾回收，只对这个连通块进行点分治，维护好信息后再连接回去即可。为了方便处理，对点分树上每个点的子节点进行记录。

实现时，我对于原树，平衡树，点分树使用了三个结构体来维护，便于操作和调试，平衡树用的 Treap" role="presentation">Treap，用结构体封装后会显著变快。

code:" role="presentation">code:

#include<bits/stdc++.h> #define maxn 200010 #define maxm 4000010 #define mod 1000000000 #define alpha 0.76 using namespace std; typedef long long ll; template<typename T> inline void read(T &x) { x=0;char c=getchar();bool flag=false; while(!isdigit(c)){if(c=='-')flag=true;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} if(flag)x=-x; } int n; ll ans; struct Graph { int d[maxn],de[maxn],f[maxn][20],val[maxn]; struct edge { int to,nxt,v; }e[maxn]; int head[maxn],edge_cnt; void add(int from,int to,int val) { e[++edge_cnt]=(edge){to,head[from],val}; head[from]=edge_cnt; } void insert(int x,int fa,int v) { if(fa) add(fa,x,v),add(x,fa,v); f[x][0]=fa,de[x]=de[fa]+1,d[x]=d[fa]+v; for(int i=1;i<=17;++i) f[x][i]=f[f[x][i-1]][i-1]; } int lca(int x,int y) { if(de[x]<de[y]) swap(x,y); for(int i=17;i>=0;--i) if(de[f[x][i]]>=de[y]) x=f[x][i]; if(x==y) return x; for(int i=17;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int dis(int x,int y) { return d[x]+d[y]-d[lca(x,y)]*2; } }G; struct Treap { int tot,top; int st[maxm]; struct node { int val,key,cnt,siz; int ch[2]; }t[maxm]; int add(int v) { int x; if(top) x=st[top--]; else x=++tot; t[x].ch[0]=t[x].ch[1]=0,t[x].val=v,t[x].key=rand(),t[x].siz=t[x].cnt=1; return x; } void del(int x) { if(!x) return; st[++top]=x,del(t[x].ch[0]),del(t[x].ch[1]); } void pushup(int x) { t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt; } void rotate(int &x,int k) { int y=t[x].ch[k^1]; t[x].ch[k^1]=t[y].ch[k],t[y].ch[k]=x; pushup(x),pushup(y),x=y; } void insert(int &x,int v) { if(!x) { x=add(v); return; } if(v==t[x].val) { t[x].cnt++,pushup(x); return; } int k=(v>t[x].val); insert(t[x].ch[k],v); if(t[x].key<t[t[x].ch[k]].key) rotate(x,k^1); pushup(x); } int query(int x,int v) { if(!x) return 0; if(v<t[x].val) return query(t[x].ch[0],v); return t[t[x].ch[0]].siz+t[x].cnt+query(t[x].ch[1],v); } }Tr; struct Tree { int tot,root; int siz[maxn],ma[maxn],fa[maxn],rt1[maxn],rt2[maxn]; bool vis[maxn]; vector<int> ve[maxn]; void dfs_root(int x,int fath) { siz[x]=1,ma[x]=0; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(vis[y]||y==fath) continue; dfs_root(y,x),siz[x]+=siz[y]; ma[x]=max(ma[x],siz[y]); } ma[x]=max(ma[x],tot-siz[x]); if(ma[x]<ma[root]) root=x; } void dfs_dis(int x,int fath,int dis,int id) { Tr.insert(rt1[id],dis-G.val[x]); if(fa[id]) Tr.insert(rt2[id],G.dis(x,fa[id])-G.val[x]); for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(vis[y]||y==fath) continue; dfs_dis(y,x,dis+G.e[i].v,id); } } void solve(int x) { int now=tot; vis[x]=true,dfs_dis(x,0,0,x); for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(vis[y]) continue; root=0,tot=siz[y]; if(siz[y]>siz[x]) tot=now-siz[x]; dfs_root(y,x),fa[root]=x,ve[x].push_back(root),solve(root); } } void del(int x) { vis[x]=false; for(int i=0;i<ve[x].size();++i) del(ve[x][i]); Tr.del(rt1[x]),Tr.del(rt2[x]),rt1[x]=rt2[x]=0,ve[x].clear(); } void rebuild(int x) { root=0,tot=Tr.t[rt1[x]].siz,del(x),dfs_root(x,0); for(int i=0;i<ve[fa[x]].size();++i) if(ve[fa[x]][i]==x) ve[fa[x]][i]=root; fa[root]=fa[x],solve(root); } void insert(int x,int fath) { fa[x]=fath,ve[fath].push_back(x),vis[x]=true; for(int i=x;i;i=fa[i]) { if(fa[i]) { int d=G.dis(fa[i],x); ans+=Tr.query(rt1[fa[i]],G.val[x]-d)-Tr.query(rt2[i],G.val[x]-d); Tr.insert(rt2[i],d-G.val[x]); } Tr.insert(rt1[i],G.dis(i,x)-G.val[x]); } int p=0; for(int i=x;fa[i];i=fa[i]) if(Tr.t[rt1[i]].siz>Tr.t[rt1[fa[i]]].siz*alpha) p=fa[i]; if(p) rebuild(p); } }T; int main() { read(n),read(n),T.ma[0]=n; for(int i=1;i<=n;++i) { int fa,v; read(fa),read(v),read(G.val[i]),fa^=ans%mod; G.insert(i,fa,v),T.insert(i,fa),printf("%lldn",ans); } return 0; }