题解 CF1311E 【Construct the Binary Tree】

· · 题解

为啥n,d\le 5000啊，我搞了个线性做法

首先最小值是很好求的：构建一棵满二叉树。令fa(i)=\lfloor\frac{i}{2}\rfloor即可。
同时，最大值显然是链的情况。
对于一般情况，考虑从满二叉树向链调整。每次把编号最大的，不在链上的点挂到链上。假设现在考虑i，链的最下端是pos。

若需要增加的深度rest\le dep(pos)+1-dep(i)，那么i需要成为pos的第 dep(pos)+1-dep(i)-rest个父亲，这里直接暴力跳，因为只会跳这一次；否则直接让i成为pos的儿子，令rest减去dep(pos)+1-dep(i),继续考虑下一个点。（注意如果点在链上就不移动了）

我这里取1,2,4,8,16...(2^x)作为初始的链。
时间复杂度显然\mathcal O(n)

/**********/
#define MAXN 200011
ll fa[MAXN],dep[MAXN];
void work()
{
    ll n=read(),sum_dep=read(),cur=0,pos;
    dep[0]=-1;
    for(ll i=1;i<=n;++i)
    {
        fa[i]=i>>1;dep[i]=dep[i>>1]+1;cur+=dep[i];
        if((i&(i-1))==0)pos=i;
    }
    sum_dep-=cur;
    if(sum_dep<0){puts("NO");return;}
    if(sum_dep==0)
    {
        puts("YES");
        for(ll i=2;i<=n;++i)printf("%lld ",fa[i]);
        puts("");
        return;
    }
    for(ll i=n;i;--i)
    {
        if((i&(i-1))==0)continue;
        sum_dep-=dep[pos]+1-dep[i];
        if(sum_dep<=0)
        {
            while(sum_dep)pos=fa[pos],++sum_dep;
            sum_dep=0;
            fa[i]=pos;break;
        }
        fa[i]=pos,dep[i]=dep[pos]+1,pos=i;
    }
    if(sum_dep)puts("NO");
    else
    {
        puts("YES");
        for(ll i=2;i<=n;++i)printf("%lld ",fa[i]);
        puts("");
    }

}
int main()
{
    ll t=read();
    while(t--)work();
}