可以用堆做到 $\mathcal O(n\log n)$ ，也可以用更加优秀的斜率优化实现 $\mathcal O(n)$。
题目链接
考虑按照 $dep$ 分层。记 $cnt_{dep}$ 表示深度为 $dep$ 的点数。考虑从大到小枚举 $k$，将对于每个 $k$ 的最优解都求出来。
在 $k$ 足够大时，显然一次能且仅能选择同一层的点，即 $ans_k=\max {dep_i}$。当某一时刻，$cnt_i>k$，那么我们无法在一次内选择完第 $i$ 层的点，需要将其中 $cnt_i-k$ 个点挪到下一层选取。
题目中限制了拥有父子关系的两个点无法同时选择，我们需要证明只需要将剩下的点向下挪动一层就能够得到合法解。
假设此时 $cnt_{i-1}\le k$。
我们需要在第 $i$ 次和第 $i+1$ 共选取 $2k$ 个点其中第 $i$ 层选取 $cnt_i$ 个，第 $i+1$ 层选取 $2k-cnt_i$ 个点。
1. $cnt_{i+1}<2k-cnt_i$：第 $i+1$ 天未取满 $k$ 个点，并不影响结果。
2. $cnt_{i+1}>2k-cnt_i$：将第 $i+1$ 层多余的点挪向第 $i+2$ 层，这显然是一个相同的子问题。
3. $cnt_i>2k$：将第 $i$ 层多余的点和第 $i+1$ 层所有点挪向第 $i+2$ 层，这显然又是一个相同的子问题。
而这 $2k$ 个点拥有父子关系的点对数 $<k$，故一定能找到合法方案。
也可以感性理解，既然当 $k’>k$ 时，被选中的点可以在当层选择，那么挪到下一层就更容易有合法方案了。
由上面的结论我们可以得到，我们始终可以把操作一次多余的点挪向下一层，保证每层的点数 $\le k$，最多有 $n$ 层。
这个时候暴力维护是不行的，因为我们并不关心多出来的点来自哪一层，我们尝试将多层放在一起合并后维护。
我们于是就维护的就是一段区间 $[l,r]$，表示连续 $r-l+1$ 天仅选取第 $[l,r]$ 层的点，且一定取完，即 $\sum_{i=l}^r cnt_i\le (r-l+1)\times k$。
故我们只需要用维护区间，每次将堆顶不合法区间取出，向下合并即可。
时间复杂度 $\mathcal O(n\log n)$ ，比隔壁斜率优化 $\mathcal O(n)$ 要慢，但也算提供新的思路吧。
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;
}
|