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

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

来源：花匠小妙招时间：2024-12-11 18:18

丸了丸了毒瘤实锤了，110行的紫荆花之恋了解一下？

只能说这道题的细节不是一般的多，我会尽量详细的在这篇题解里列举一下

前置芝士:动态点分治(点分树)

如果不知道什么是动态点分治(或者点分树)的话还是暂且不要淦这题了，拿这题去练动态点分治的手会让你留下心里阴影

关于动态点分治这个技术可以去自行百度一下，做几道例题来学习一下

前置芝士:高速平衡树

这里的高速平衡树指的是除了splay和fhqtreap以外的所有平衡树(这两个平衡树真的很慢)，如果不会这些平衡树的话请出门左转模板区

本题题解

一句话题意，维护一颗树支持动态的插入叶子，每个边上有边权，每个点上有点权，每次插入一个节点之后询问树上有多少点对满足两个点的点权之和大于边权

强制在线(对，这才是万恶之源)

那么让我们来简单的分析一下题目的思路

首先可以想到的是我们求出答案的方式应该是插入一个节点之后p询问一下树上有多少个点v和p的距离小于v,p的点权之和，然后把这些点的数目加到答案中去就可以得到插入了p之后的答案了

所以说现在的问题就是询问树上一个点到其他所有点的信息的问题

如果你对动态点分治(点分树)这个技术足够熟练的话应该可以想到我们是可以用点分树去解决这个问题的(这是动态点分治的两个常见用法,一个是询问树上的某一个点到其他所有点的信息，另一个是树上二分寻找关键点)

我们就对这个树建立起一颗点分树(让我们暂时忽略复杂度问题)

现在让我们来看一看这颗点分树都需要维护什么信息呢？

part1:处理询问

我们现在希望询问对于树上一个点u，有多少个点v的点权加起来大于他们之间的距离

那么我们可以考虑遍历u在点分树上的所有祖先g(显然这些祖先不会太多)，然后考虑一条形如u-v-g的路径是否合法

那么我们设u-g的路径为d_{u},v-g的路径长度为d_{v},显然dis(u,v)=d_{u}+d_{v}，根据题意，一个点对u,v合法当且仅当dis(u,v) leq r_{u}+r_{v}，换句话说就是d_{u}+d_{v} leq r_{u}+r_{v}，我们对这个不等式做些小小的变换，那么我们就可以得到这个式子

d_{v}-r_{v} leq r_{u}-d_{u}

换句话说我们在每一层的祖先g处需要查询的东西就是有多少个v他的d_{v}-r_{v}比r_{u}-d_{u}小，那么我们可以使用平衡树来维护这些d_{v}-r_{v}的值，(这里之所以不使用权值线段树和权值树状数组是因为根本无法离散化所以只能上平衡树),这样的话我们就可以求出有多少个形如u-g-v的路径了，只是这样有一个问题，就是我们可能考虑了的路径并不是简单的路径，换句话说即使切掉g，u,v还是在同一个联通块里

那其实也很简单，对于切掉g之后形成的若干个联通块，我们每个块开一个平衡树还是存同样的值，查询的时候用总的减去和自己在同一个联通块里的就行了

那么我们总结一下就是我们点分树上每一个节点都需要开一个vector

vector里面存一个三元组(g,dis,tree)表示这个节点的一个祖先编号，到这个祖先的距离，以及在切掉这个祖先之后，这个点所在的联通块所在的平衡树编号(也就是说，同一个平衡树会被不同的节点存很多次)

然后每一个点开一个平衡树，存的是点分治到这个点g的时候，和g在同一个联通中的点v的d_{v}-r_{v}值

查询树上的一个点u到树上的其他点v中，有多少个合法(u,v)对的算法流程如下

枚举u的vector中的所有元素，对于一个祖先g，在这个点平衡树上查一下有几个元素小于等于r_{u}-d_{u}，加到答案里，然后在这个vector里存的平衡树中查一下有几个元素小于r_{u}-d_{u}答案减去这个值。如此这般迭代我们就能获得答案了,对了，我们还需要查一下这个点自己的平衡树里面有多少点的值小于-r_{u}(因为自己到自己的距离是0)

part2:定期重构点分树

然后问题来了，我们总不能每次都点分治啊，这样的话我们只会得到一个O(n^2logn)的垃圾做法

那么我们可以想一个类似于替罪羊树的思想，就是我们每次插入一个节点的时候检查一下是否存在一对父子使得父亲的size×a小于孩子的size，如果存在这样的不平衡关系我们就找到最高的点，然后重构这个点所在的点分树子树

好了现在的问题就是我们的点分树维护的信息已经相当的复杂了，重构整颗点分树就算了，问题是重构一个点分树的子树的时候我们进行的操作将会相当的难受了

但是就算难受我们还是得写

所以我们慢慢的推我们需要在点分树上维护什么附加的信息才能让我们可以重构这个点分树的一个子树

首先我们需要的信息是这个点的子树里都有谁，所以我们每个节点暴力的开一个vector存他的所有孩子都是谁，同时我们在重构点分树的时候还需要清空一些平衡树(因为要重新插入)所以我们每个节点开一个vector存的是切掉这个点之后，存储剩下的各个联通块信息的平衡树，也就是你查询的时候减掉的那颗平衡树

好了那么现在我们要重构一个点p在点分树中的子树了

怎么办呢?

其实也很简单我们清空该清空的东西留下该留下的东西然后点分治就行了

我们需要清空的东西有

1.这个子树中所有点的平衡树

2.这个子树中所有用来减的平衡树

3.这个子树中所有点用来存自己孩子的vector

4.这个子树中所有点的存自己周围一圈平衡树的vector

但是最重要的还是每个点用来存自己祖先的vector

如果我们在每一层点分治的时候都在这个存祖先的vector里面push我们该push的元素的话，你会发现vector中元素的顺序刚好是所有祖先按照深度排序的顺序，所以我们清空的时候不停的pop_back直到我们把p给pop出来为止

然后清空了这些之后我们访问一遍p的存孩子标记然后把对应的节点都打上标记跑一遍点分治就可以了

part3点分治

当然点分治的过程相对来讲还是比较亲切的(其实这题哪个部分都不难写，就是叠起来就十分的要命另外细节超级多)

我们十分套路对目标联通块进行找重心操作,找到重心之后我们考虑构造这一层的点分树

首先先把这个联通块里的所有点push到g的孩子vector里没有任何问题

然后接下来dfsg的每一个子树，对于每一个子树里的元素v我们把(g,dis(g,v),tree)这个三元组插到v的vector里去

然后在上述dfs的过程中我们顺手把平衡树新建出来顺便把每个节点的d_{v}-r_{v}插到平衡树中去就可以了

part4插入一个节点

嗯，最要命的东西来了

我们需要插入一个节点，把他挂在u上

我们具体的算法流程如下

首先把u的祖先vector复制一份给p

然后for一遍这个vetor，里面所有的dis+=u和p之间的距离，同时在这个vector记录的平衡树以及祖先g的平衡树中插入dis-r_{p}这个值

接下来在p的vector中插入(u,dis(u,p),tree)这个三元组，(当然你需要把p的平衡树开出来)同时你还需要把u的存平衡树的vector中插入一个关于p的平衡树，并且在这个平衡树中插入dis(u,p)-r_{p}这个值，同时你还需要把p的平衡树也给开出来同时插入-r_{p}这个值

接下来事情还没有结束我们for一遍p的vector，并在这些祖先的孩子vector当中插入p

最后我们扫描一遍p的vector检测有无违反a平衡条件的父子对，如果有，就重构那个最高的节点所在的子树

对了，插入1号节点记得特判

关于高速平衡树

splay实在是太慢了

可我是个splay党啊，只会splay怎么办啊，不想写treap啊

写bst啊，只要数据随机就是最快的二叉搜索树

可是9,10两个点卡bst啊

替罪羊树啊,简单粗暴的平衡树a取0.8就可以通过本题了

110行紫荆花之恋你值得拥有

上代码~

// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<vector> using namespace std;const int N=1e5+10;const int M=6*1e6+10;typedef long long ll;const ll mod=1e9; int t;int n;ll lastans; namespace SC//简易替罪羊树模板 { int s[M][2];int fa[M];int siz[M];int val[M];int tr[N];int hd;int st[M];int tp;int ct; inline int chk(){return tp?st[tp]:ct+1;} inline int rus(){return tp?st[tp--]:++ct;}inline void rls(const int& x){st[++tp]=x;} inline void del(const int& x) {if(s[x][0])del(s[x][0]);if(s[x][1])del(s[x][1]);s[x][0]=s[x][1]=0;rls(x);} inline int gc(const int& x){return s[fa[x]][1]==x;} struct spt { int rt; inline void itw(const int& p){if(s[p][0])itw(s[p][0]);tr[++hd]=p;if(s[p][1])itw(s[p][1]);} inline int build(int l,int r) { if(l>r)return 0;int mid=(l+r)/2;int p=tr[mid];s[p][0]=build(l,mid-1); s[p][1]=build(mid+1,r);fa[s[p][0]]=p;fa[s[p][1]]=p;siz[p]=siz[s[p][0]]+1+siz[s[p][1]]; return p; } inline void ins(const int& va) { int hi=-1;int p=0; for(int tw=rt;tw;tw=s[p][val[p]<=va])//a取0.8 {p=tw;siz[p]++;if(fa[p]!=0&&fa[p]!=rt&&hi==-1&&siz[p]*5>=siz[fa[p]]*4)hi=fa[p];} int np=rus();fa[np]=p;s[p][val[p]<=va]=np;val[np]=va;siz[np]=1; if(hi!=-1){int d=fa[hi];int t=gc(hi);hd=0;itw(hi);s[d][t]=build(1,hd);fa[s[d][t]]=d;} } inline int qry(const int& va) {int ret=0;for(int p=rt;p;)if(val[p]<=va)ret+=siz[s[p][0]]+1,p=s[p][1];else p=s[p][0];return ret;} inline int rebuild(int* a,int l,int r) { if(l>r)return 0;int mid=(l+r)/2;int p=rus();val[p]=a[mid]; s[p][0]=rebuild(a,l,mid-1);s[p][1]=rebuild(a,mid+1,r); fa[s[p][0]]=p;fa[s[p][1]]=p;siz[p]=siz[s[p][0]]+1+siz[s[p][1]];return p; } inline void clear(){del(rt);}inline void ih(int* a,int S){rt=rebuild(a,0,S);fa[rt]=0;} }; } namespace VDC_tree//点分树 { int v[2*N];int x[2*N];int ct;int al[N];int val[2*N];bool cut[N];int siz[N];int w[N]; struct data{int f;int dis;SC::spt sp;};vector <data> ve[N]; vector <int> so[N];vector <SC::spt> nw[N];SC::spt sct[N];int ndep[N];int tp;int* mdep;int tot; inline void add(int u,int V,int va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} inline int dfs1(int u,int f)//找重心 {siz[u]=1;for(int i=al[u];i;i=x[i])if(v[i]!=f&&cut[v[i]])siz[u]+=dfs1(v[i],u);return siz[u];} inline int find(int u,int f,const int& tot) { for(int i=al[u];i;i=x[i]) if(v[i]!=f&&cut[v[i]]&&2*siz[v[i]]>=tot)return find(v[i],u,tot);return u; } inline void dfs3(int u,int f,int dis,const int& g,const int& p)//处理点分树 { so[g].push_back(u);ve[u].push_back((data){g,dis,(SC::spt){p}});mdep[++tp]=dis-w[u]; for(int i=al[u];i;i=x[i])if(v[i]!=f&&cut[v[i]])dfs3(v[i],u,dis+val[i],g,p); } inline void solve(int u)//点分治 { dfs1(u,0);int g=find(u,0,siz[u]);cut[g]=false;so[g].clear();so[g].push_back(g); if(siz[u]==1){ndep[0]=-w[u];sct[g].ih(ndep,0);return;}mdep=ndep;tp=-1;tot=0; for(int i=al[g];i;i=x[i]) { if(!cut[v[i]])continue;mdep=mdep+tp+1;tot+=tp+1;tp=-1;dfs3(v[i],g,val[i],g,SC::chk()); SC::spt tre;sort(mdep,mdep+tp+1); tre.ih(mdep,tp);nw[g].push_back(tre); }tot+=tp+1;ndep[tot]=-w[g];sort(ndep,ndep+tot+1);sct[g].ih(ndep,tot); for(int i=al[g];i;i=x[i])if(cut[v[i]])solve(v[i]); } inline void rebuild(int p)//重构前的清空函数 { vector <int>:: iterator it;vector <SC::spt>:: iterator it1; for(it=so[p].begin();it!=so[p].end();++it)cut[*it]=true; for(it=so[p].begin();it!=so[p].end();++it)sct[*it].clear(); for(it=so[p].begin();it!=so[p].end();++it) {for(it1=nw[*it].begin();it1!=nw[*it].end();++it1)it1->clear();nw[*it].clear();} for(it=so[p].begin();it!=so[p].end();++it) if(*it!=p)while(1)if(ve[*it].rbegin()->f==p){ve[*it].pop_back();break;}else ve[*it].pop_back(); solve(p); } inline int ins(int p,int u,int va,int we)//插入一个点 { add(u,p,va);add(p,u,va);w[p]=we;vector <data>:: iterator it,it1,it2;int res=0; for(ve[p]=ve[u],it=ve[p].begin();it!=ve[p].end();++it) it->dis+=va,it->sp.ins(it->dis-we),sct[it->f].ins(it->dis-we); SC::spt tre;ndep[0]=va-we;tre.ih(ndep,0);ve[p].push_back((data){u,va,tre}); nw[u].push_back(tre);sct[u].ins(va-we);ndep[0]=-we;sct[p].ih(ndep,0);so[p].push_back(p); for(it=ve[p].begin();it!=ve[p].end();++it)so[it->f].push_back(p); for(it1=ve[p].begin(),it2=it1,++it2;it2!=ve[p].end();++it2,++it1) if(so[it1->f].size()*4<=so[it2->f].size()*5){rebuild(it1->f);break;} res+=sct[p].qry(we)-1; for(it=ve[p].begin();it!=ve[p].end();++it) res+=sct[it->f].qry(we-it->dis)-it->sp.qry(we-it->dis);return res; } inline void ih(int we){w[1]=we;ndep[0]=-we;sct[1].ih(ndep,0);so[1].push_back(1);} } int main() { scanf("%d",&t);scanf("%d",&n); int f;int va;int we;scanf("%d%d%d",&f,&va,&we);VDC_tree::ih(we);printf("0n"); for(int i=2;i<=n;i++) { scanf("%d%d%d",&f,&va,&we);f^=(lastans)%mod; lastans+=VDC_tree::ins(i,f,va,we);printf("%lldn",lastans); }return 0;//拜拜程序~ }