可以用堆做到 ,也可以用更加优秀的斜率优化实现 。
题目链接
考虑按照 分层。记 表示深度为 的点数。考虑从大到小枚举 ,将对于每个 的最优解都求出来。
在 足够大时,显然一次能且仅能选择同一层的点,即 。当某一时刻,,那么我们无法在一次内选择完第 层的点,需要将其中 个点挪到下一层选取。
题目中限制了拥有父子关系的两个点无法同时选择,我们需要证明只需要将剩下的点向下挪动一层就能够得到合法解。
假设此时 。
我们需要在第 次和第 共选取 个点其中第 层选取 个,第 层选取 个点。
1. :第 天未取满 个点,并不影响结果。
2. :将第 层多余的点挪向第 层,这显然是一个相同的子问题。
3. :将第 层多余的点和第 层所有点挪向第 层,这显然又是一个相同的子问题。
而这 个点拥有父子关系的点对数 ,故一定能找到合法方案。
也可以感性理解,既然当 时,被选中的点可以在当层选择,那么挪到下一层就更容易有合法方案了。
由上面的结论我们可以得到,我们始终可以把操作一次多余的点挪向下一层,保证每层的点数 ,最多有 层。
这个时候暴力维护是不行的,因为我们并不关心多出来的点来自哪一层,我们尝试将多层放在一起合并后维护。
我们于是就维护的就是一段区间 ,表示连续 天仅选取第 层的点,且一定取完,即 。
故我们只需要用维护区间,每次将堆顶不合法区间取出,向下合并即可。
时间复杂度 ,比隔壁斜率优化 要慢,但也算提供新的思路吧。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| #include<iostream> #include<cstdio> #include<queue> #include<bitset> #define ll long long using namespace std; const int N=1e6+10; template<class T> inline void read(T &x) { x=0;int f=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(f)x=-x; } template<class T,class ...T1> inline void read(T &x,T1&...x1) { read(x),read(x1...); } struct Node { int l,r,cnt; inline bool operator<(const Node &rhs)const { return (ll)cnt*(rhs.r-rhs.l+1)<(ll)rhs.cnt*(r-l+1); } inline bool check(int k)const { return (ll)(r-l+1)*k<cnt; } }; int n,m; int query[N],ans[N]; int cnt[N],dep[N]; int ed[N]; bool vis[N]; priority_queue<Node>q; int main() { read(n,m); for(int i=1;i<=m;i++) read(query[i]); ++cnt[dep[1]=1]; int res=1; for(int i=2;i<=n;i++) { int fa; read(fa); ++cnt[dep[i]=dep[fa]+1]; res=max(res,dep[i]); } for(int i=1;i<=n;i++) { ed[i]=i; q.push((Node){i,i,cnt[i]}); } for(int k=1e6;k>=1;k--) { while(q.top().check(k)) { Node x=q.top(); q.pop(); if(vis[x.l]) continue; vis[x.r+1]=1; res=max(res,ed[x.l]=ed[x.r+1]); cnt[x.l]+=cnt[x.r+1]; q.push((Node){x.l,ed[x.l],cnt[x.l]}); } ans[k]=res; } for(int i=1;i<=m;i++) printf("%d ",ans[query[i]]); return 0; }
|
Gitalk 加载中 ...