Codeforces 1311 E Construct the Binary Tree ——构造深度之和固定的二叉树

本文主要是介绍Codeforces 1311 E Construct the Binary Tree ——构造深度之和固定的二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

告诉你n和d。构建一个顶点为1，有n个点的二叉树，其所有节点深度之和为d，并且输出2-n这些点的父亲。

题解：

我是想先用最小的方法构建二叉树，然后一个点一个点往最左端移动，，但是这样太过麻烦了。然后发现可以先用最大方法构造二叉树，然后一个点一个点往前移即可
fa[i]表示当前点的当前父亲
num[i]表示深度为i时的节点数
val[i][j]表示深度为i时，第j个数是什么。
由于方便，我默认深度+1

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int num[N],val[N][N],fa[N];
int n,m;
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);if(n*(n-1)/2<m){printf("NO\n");continue;}m=n*(n-1)/2-m;for(int i=1;i<=n;i++)num[i]=1,val[i][1]=i,fa[i]=i-1;int now=2;for(int i=n;m&&i>now;i--){int ret=min(m,i-now);m-=ret;val[i-ret][++num[i-ret]]=i;fa[i]=val[i-ret-1][(num[i-ret]+1)/2];if(num[now]==1<<now-1)now++;}if(m)printf("NO\n");else{printf("YES\n");for(int i=2;i<=n;i++)printf("%d%c",fa[i]," \n"[i==n]);}}return 0;
}

这篇关于Codeforces 1311 E Construct the Binary Tree ——构造深度之和固定的二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---