P5384 [Cnoi2019] 雪松果树 题解
传送门前言
一年一度，生长在高山上的雪松果树又结果了。
第二天,雪松果树长成了一颗参天大树, 上面长满了雪松果。
求雪松果树生长周期
整活向题解。
奋力卡常 3h，纪念一下。
是的，我一个人的提交占了三页。
题意简述
给一棵树，查询某节点的 \(k\)-cousin。
题解
基本思路
虽然有很多更优的做法，但是我们考虑线段树合并。
在每个节点建一棵权值线段树，维护子树内每个深度的节点个数。
把询问离线下来，对整棵树进行 dfs，将每棵子树的线段树合并到该节点的线段树，之后处理该节点的询问。
这里需要将询问转化为求原询问节点的 \(k\)-father 的 \(k\)-son 数量减一。
求 \(k\)-father 可以使用倍增。
于是我们可以写出如下代码：
#include <cstdio>#include <vector>#define N 1000005int n,q,ans,fa,rt;int hed,tal,nxt,cnte;void adde(int u,int v) {tal[++cnte]=v,nxt=hed,hed=cnte;}struct query {int id,k;};std::vector<query> a;struct sgt{ #define mid (lb+rb>>1) #define pushup(x) d=d]+d] int d,ls,rs,idx; void modify(int &x,int t,int lb,int rb) { if(!x) x=++idx; d++; if(lb==rb) return; if(t<=mid) modify(ls,t,lb,mid); else modify(rs,t,mid+1,rb); } int query(int x,int t,int lb,int rb) { if(!x) return 0; if(lb==rb) return d; if(t<=mid) return query(ls,t,lb,mid); else return query(rs,t,mid+1,rb); } int merge(int x,int y,int lb,int rb) { if(!x||!y) return x+y; if(lb==rb) {d+=d;return x;} ls=merge(ls,ls,lb,mid); rs=merge(rs,rs,mid+1,rb); pushup(x);return x; } #undef mid #undef pushup} tr;void dfs(int x,int f,int dep){ tr.modify(rt,dep,1,n); for(int i=hed;i;i=nxt) if(tal!=f) dfs(tal,x,dep+1),rt=tr.merge(rt,rt],1,n); for(int i=0;i<a.size();i++) ans.id]=tr.query(rt,dep+a.k,1,n)-1;}main(){ scanf("%d%d",&n,&q); for(int i=2;i<=n;i++) scanf("%d",&fa),adde(fa,i); for(int i=1;i<=20;i++) for(int j=2;j<=n;j++) fa=fa]; for(int i=1;i<=q;i++) { int u,k; scanf("%d%d",&u,&k); int d=0; for(int j=20;j>=0;j--) if(d+(1<<j)<=k) u=fa,d+=1<<j; if(u) a.push_back({i,k}); } dfs(1,0,1); for(int i=1;i<=q;i++) printf("%d ",ans);}像这样。
优化
如果你按照我们刚才的思路写出了如上代码，那么恭喜你，你可以获得 \(40\) 分的好成绩。
于是我们需要优化。
由于剩下的点都 MLE 了，所以需要优化空间。
首先，注意到线段树的数组开得很大，这是因为每个节点都有一棵线段树。然而我们线段树合并统计答案时，当一个节点的答案被合并到父节点时，这个节点的线段树就再也用不上了。所以我们回收这棵线段树上的节点。这样，线段树的空间只需开到 \(4e6\)。
于是得到这样一棵线段树：
struct sgt{ #define mid (lb+rb>>1) int d,ls,rs,idx; int st,tp; //回收 void modify(int &x,int t,int lb,int rb) { if(!x) x=tp?st:++idx; //使用先前回收的空间 d++; if(lb==rb) return; if(t<=mid) modify(ls,t,lb,mid); else modify(rs,t,mid+1,rb); } int query(int x,int t,int lb,int rb) { if(!x) return 0; if(lb==rb) return d; if(t<=mid) return query(ls,t,lb,mid); return query(rs,t,mid+1,rb); } int merge(int x,int y,int lb,int rb) { if(!x||!y) return x|y; d+=d; if(lb<rb) ls=merge(ls,ls,lb,mid), rs=merge(rs,rs,mid+1,rb); d=ls=rs=0,st[++tp]=y; //回收空间 return x; } #undef mid} tr;其次，我们开了 \(1e6\) 个 vector 来存储询问，这样消耗的空间是无法接受的，所以需要改变询问的存储方式。
可以使用一种链式前向星式的做法：
int qh; //链头int qnxt; //下一个询问的编号struct query{ int v,k; //v:u的k-father} a;void addq(int x){ qnxt=qh.v]; qh.v]=x;}我们看到用来求 k-father 的倍增数组也占了很大的空间，于是改用树剖。
int dep,son,siz,top,dfn,li,id;void dfs1(int x) //正常的树剖{ siz=1,dep=dep]+1; for(int i=hed;i;i=nxt) if(!siz]) { dfs1(tal); siz+=siz]; if(siz]>siz]) son=tal; }}void dfs2(int x,int tp) //正常的数剖{ li=++id]=x,top=tp; if(!son) return; dfs2(son,tp); for(int i=hed;i;i=nxt) if(!top]) dfs2(tal,tal);}int anc(int u,int k){ int v=u; while(v&&dep-dep]<k) v=fa]; if(!v) return 0; //没有k-father /* 例：u=8,k=4,dep=7 跳到了重链1-6 1-2-3-4-5-6 ^ ^ v top kfa dep=dep-k dfn+dep-dep=dfn li]=3 */ return li]+dep-k-dep]];}像这样。
终极优化
如果你使用如上方式优化，那么恭喜你，可以不再 MLE 并获得 \(76\) 分至 \(92\) 分不等的好成绩。
当然，如果你的写法常数更小卡过去了也行。
为什么不能 AC 呢？
让我们看看最初的代码中调用线段树的部分：
rt=tr.merge(rt,rt],1,n);线段树的值域是 \(n\)。
然而，我们的线段树维护的是深度。
所以值域应该为深度的最大值。
代码
#include <cstdio>#define N 1000002int n,q,md,ans,fa,rt;int hed,tal,nxt,cnte;void adde(int u,int v) {tal[++cnte]=v,nxt=hed,hed=cnte;}int qh,qnxt;int av,ak;void addq(int x) {qnxt=qh],qh]=x;}int dep,son,siz,top,dfn,li,id;void dfs1(int x){ siz=1,dep=dep]+1; if(dep>md) md=dep; for(int i=hed;i;i=nxt) if(!siz]) { dfs1(tal),siz+=siz]; if(siz]>siz]) son=tal; }}void dfs2(int x,int tp){ li=++id]=x,top=tp; if(!son) return; dfs2(son,tp); for(int i=hed;i;i=nxt) if(!top]) dfs2(tal,tal);}int anc(int u,int k){ int v=u; while(v&&dep-dep]<k) v=fa]; if(!v) return 0; return li]+dep-k-dep]];}struct sgt{ #define mid (lb+rb>>1) int d,ls,rs,idx; int st,tp; void modify(int &x,int t,int lb,int rb) { if(!x) x=tp?st:++idx; d++; if(lb==rb) return; if(t<=mid) modify(ls,t,lb,mid); else modify(rs,t,mid+1,rb); } int query(int x,int t,int lb,int rb) { if(!x) return 0; if(lb==rb) return d; if(t<=mid) return query(ls,t,lb,mid); return query(rs,t,mid+1,rb); } int merge(int x,int y,int lb,int rb) { if(!x||!y) return x|y; d+=d; if(lb<rb) ls=merge(ls,ls,lb,mid), rs=merge(rs,rs,mid+1,rb); d=ls=rs=0,st[++tp]=y; return x; } #undef mid} tr;void dfs3(int x){ tr.modify(rt,dep,1,md); for(int i=hed;i;i=nxt) if(tal^fa) dfs3(tal),rt=tr.merge(rt,rt],1,md); for(int i=qh;i;i=qnxt) ans=tr.query(rt,dep+ak,1,md)-1;}main(){ scanf("%d%d",&n,&q); for(int i=2;i<=n;i++) scanf("%d",&fa),adde(fa,i); dfs1(1),dfs2(1,1); for(int i=1;i<=q;i++) { int u,k; scanf("%d%d",&u,&k); av=anc(u,k),ak=k,addq(i); } dfs3(1); for(int i=1;i<=q;i++) printf("%d ",ans);}<hr>
\[\Huge End\]
页:
[1]