P3571 题解

· · 题解

实现上与已有所有题解不同。这份代码是可以通过测试的。分析部分有参考出题人（也许是吧）的题解。

首先我们发现，正着搞会有很多限制，所以考虑倒着搞，每次去掉一些叶子，至多 k 个，而且没有任何其余限制。

令树高为 H，考虑第 h 层，令 s_h 表示整棵树上深度不小于 h 的节点的个数。那么我们至少需要操作 \left\lceil\dfrac{s_{h+1}}{k}\right\rceil 次才可以将深度大于等于 h+1 的所有节点去掉。而对于深度为 1 到 h 的节点，容易知道不存在任何一次操作能同时删光两层，因为每次删完后，树都是连通的，所以这两层中一定存在一个节点是另一个的祖先，而一个还存在的节点的祖先必然不是叶子节点。那么想要删光这 h 层就至少要操作 h 次，所以答案 ans\ge h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil。由于答案对于每个 h 都满足上式，所以 ans\ge \max\limits_{h\le H}\bigg\{h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil\bigg\}。

那么可不可以取等呢？我们设计贪心策略如下：每次去掉深度最大的 k 个叶子节点点，如果有相同深度的就随便去掉，如果叶子节点不足 k 个就全部去掉，这样一定能保证取的是叶子节点，并且尽量取满 k 个，并且在去掉深度大于等于 h+1 的所有节点后才去掉前 h 层的点。

然后进行分类讨论：

  1. 假设当前树高为 H，如果当前树的宽度不大于 k，很明显只需要 H 次删光，并且因为每次至多删光一层，所以也只能至少 H 次删光，此时 ans 必然取等。

  2. 如果当前树的宽度不大于 k，那么我们可以选择它最深的 k 个叶子，并将它们删除，它们的深度分别为 d_1\ge d_2\ge...\ge d_k。同时，最深的一层，即深度为 H 的一层必定删光，所以新树高 H'=H-1。

    1. 对于所有 h<d_k，在删除这 k 个叶子后，它们对应的 h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil 刚好减少 1。

    2. 对于所有 h\ge d_k，我们可以发现 h>d_k 的所有层点数不超过下一层的点数加上这一层的叶子数，都不超过 k 。所以第 h+1 层的点数 < k，对于所有 h\ge d_k，有 h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil\le h+1+\left\lceil\dfrac{s_{h+2}}{k}\right\rceil，而最后一层，即深度为 H'=H-1 的那一层的值为 H-1，所以对于所有 h\ge d_k，h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil 都小于 H-1。

综上，在这种贪心策略下，每一次操作都可以使 \max\limits_{h\le H}\bigg\{h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil\bigg\} 减小 1。

所以我们证明了 ans=\max\limits_{h\le H}\bigg\{h+\left\lceil\dfrac{s_{h+1}}{k}\right\rceil\bigg\}，要快速求对于每个 k，这个式子的最大值。将式子变一下变成 ans=\max\limits_{h\le H}\bigg\{\left\lceil\dfrac{s_{h+1}+h\times k}{k}\right\rceil\bigg\}。

容易知道对于固定的 k，分子越大，这个值单调不减，所以求分子最大值就行了。

于是题目变为给出 n 条形为 y=h\times x+s_{h+1} 的直线，要求 x=k 时的最大值， 发现就是一个李超线段树的模板。由于没有范围限制，所以至多只需要修改 \log n 级别的区间就可以了，单次修改和查询的复杂度都是 O(\log n)，所以总时间复杂度是 O(n\log n)，而且常数很小，可以通过此题。

亲测不开 O2 优化时，最慢的一个点 308ms。

ll n,qwq,mxq=0,mxd=0,l=1,r=0,a[1000010],f[1000010],t[4000010],d[1000010],s[1000010];
inline ll cal(ll x,ll v){return s[x+1]+x*v;}
void upd(ll x,ll l,ll r,ll u){
    ll &v=t[x],mid=(l+r)>>1;
    if(cal(u,mid)>cal(v,mid))swap(u,v);
    if(cal(u,l)>cal(v,l))upd(x<<1,l,mid,u);
    if(cal(u,r)>cal(v,r))upd(x<<1|1,mid+1,r,u);
}
ll query(ll x,ll l,ll r,ll v){
    if(l==r)return cal(t[x],v);
    ll mid=(l+r)>>1;
    if(v<=mid)return max(cal(t[x],v),query(x<<1,l,mid,v));
    else return max(cal(t[x],v),query(x<<1|1,mid+1,r,v));
}
int main(){
    n=read();qwq=read();d[1]=s[1]=1;
    for(ll i=1;i<=qwq;i++)mxq=max(mxq,a[i]=read());
    for(ll i=2;i<=n;i++){d[i]=d[read()]+1;s[d[i]]++;mxd=max(mxd,d[i]);}
    for(ll i=mxd-1;i;i--){s[i]+=s[i+1];upd(1,1,n,i);}
    for(ll i=1;i<=mxq;i++)f[i]=(query(1,1,n,i)-1)/i+1;
    for(ll i=1;i<=qwq;i++){write(f[a[i]]);putchar(' ');}
    return 0;
}

AC 记录