「Daily OI Round 1」Tree 题解

Acoipp · 2023-08-14 19:57:13 · 题解

下面是出题人题解：

因为是到根节点的距离，所以设根节点深度为 0，其余节点同理，题意转化为了所有节点深度和为 d。

subtask0

暴力可做，枚举每个点的父亲节点，时间复杂度 O(n!)。

subtask1

节点数量为 n 的树的节点的深度之和的种类很少，所以对于每一种深度搜索一下再剪个枝就可以了。

subtask2

很显然，构造菊花图，然后判断深度之和是否等于 d 即可。

subtask3

还是构造菊花图，但是当 n 很小的时候也可以构造出非菊花图的解，特判一下就可以了。

subtask4

给随机数算法的分。

subtask5

很显然，对于深度相同的节点，把它们的儿子都移到这个深度的某个节点下面是可行的，那么这时题目变成了每一层至少 k 个节点，除开第一层。

题目还要求最大深度最小，枚举最大深度，然后每个深度（除了根节点所在深度）都先安排 k 个点上去，剩下的点就随便选择一个小于等于当前枚举的深度安排就可以了。

如果剩下 i 个点，当前枚举深度为 x，每层安排 k 个点后深度之和 d 减去这些点的深度后为 y。

那么有解当且仅当 i \le y \le i \times x，然后构造就很简单了。

确定每个点的深度，然后深度 x 的所有点的父亲设为深度 x-1 的某个节点即可。

深度最大为 n，时间复杂度不计算排序的话是 O(\sum n)。

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll t,k,n,d,i,j,l,p,o,temp,dep[N],tot,ans[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        tot=0;
        cin>>n>>d>>k;
        if(n==1){
            if(d==0){
                cout<<"YES\n";
                continue;
            }
            else{
                cout<<"NO\n";
                continue;
            }
        }
        temp=0;
        for(i=1;i<=n;i++){
            if(i*(i+1)/2*k>d||i*k+1>n) break;
            j = d-i*(i+1)/2*k;
            l = (n-i*k-1);
            if(l*i>=j&&l<=j){
                j=i*l-j;
                temp=1;
                cout<<"YES\n";
                for(p=1;p<=i;p++){
                    for(o=1;o<=k;o++) dep[++tot]=p;
                }
                for(p=1;p<=l;p++) dep[++tot]=i;
                for(p=tot-l+1;p<=tot;p++){
                    if(dep[p]-1>=j){
                        dep[p]-=j;
                        break;
                    }
                    else j-=(dep[p]-1),dep[p]=1;
                }
                sort(dep+1,dep+tot+1);
                ans[0] = 1;
                for(p=1;p<=tot;p++) cout<<ans[dep[p]-1]<<" ",ans[dep[p]]=p+1;
                cout<<endl;
                break;
            }
        }
        if(!temp) cout<<"NO\n";
    }
    return 0;
}