CF1311E题解

PenguinJ · 2025-09-11 15:13:49 · 题解

题意

构造一棵有 n 个节点的二叉树，使所有点的深度之和为 d，根节点为 1，根节点深度为 0。

思路

深度之和达上界时树为链的形态，达下界时为满二叉树的形态。考虑初始先构造一条链，逐步向满二叉树的形态调整。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n,d,fa[5003],dep[5003],cnt[5003],sum,maxn,cur,now,minn;
vector<int>v[5003];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>d;
        sum=cur=0,maxn=n-1,minn=0,now=n;
        for(int i=2;i<=n;i++)fa[i]=i-1,cnt[i]=1,sum+=(i-1);
        cnt[1]=1,cnt[n]=0;
        for(int i=0;i<n;i++){
            v[i].clear();
            v[i].push_back(i+1);
        }
        int x=n;
        for(int i=0,b=1;x;i++,b*=2)minn+=min(x,b)*i,x-=min(x,b);
        if(sum<d||d<minn){cout<<"No\n";continue;}
        while(sum-maxn+cur+1>d){
            sum=sum-maxn+cur+1;
            int u=v[cur].back();
            cnt[u]++;cnt[fa[now]]--;
            v[cur+1].push_back(now);
            maxn--;
            fa[now]=u;
            now--;
            if(cnt[u]==2)v[cur].pop_back();
            if(!v[cur].size())cur++;
        }
        int dt=sum-d;
        fa[now]=now-dt-1;
        cout<<"Yes\n";
        for(int i=2;i<=n;i++)cout<<fa[i]<<" ";
        cout<<"\n";
    }
    return 0;
}